import random
import os
import shutil


if os.path.exists('../tests'):
    print('Directory "tests" already exists')
    shutil.rmtree('../tests', ignore_errors=False, onerror=None)

try:
    os.makedirs('../tests')
except OSError:
    pass

random.seed(239)

test_number = 1
def write_test(arr, reqs):
    global test_number
    f = "../tests/" + "0" * (2 - len(str(test_number))) + str(test_number)

    outp = open(f, "w")

    outp.write(str(len(arr)) + "\n")
    outp.write(" ".join(map(str, arr)) + "\n")

    outp.write(str(len(reqs)) + "\n")
    for r in reqs:
        if (r[0] == 0):
            outp.write("+ " + str(r[1] + 1) + " " + str(r[2] + 1) + " " + str(r[3]) + "\n")
        else:
            outp.write("? " + str(r[1] + 1) + " " + str(r[2] + 1) + "\n")

    outp.close()
    
    print("Test #" + str(test_number) + " has been generated")       

    test_number += 1

maxa = 10 ** 9
maxd = 10 ** 9
maxn = 10 ** 5
maxq = 10 ** 5

def gen_random_test(n, q, nowma, nowmd):
    arr = []
    for i in range(n):
        arr.append(random.randint(-nowma, nowma))

    reqs = []

    for i in range(q):
        #print(i)
        act = random.randint(0, 1)
        if (act == 0):
            l = random.randint(0, n - 1)
            r = random.randint(0, n - 1)
            if (l > r):
                l, r = r, l
            d = random.randint(-nowmd, nowmd)
            reqs.append([0, l, r, d])
        else:
            l = random.randint(0, n - 1)
            r = random.randint(0, n - 1)
            if (l > r):
                l, r = r, l
            reqs.append([1, l, r])

    write_test(arr, reqs)       

def gen_test_with_full_length_ap(n, q):
    arr = [random.randint(-maxa, maxa - n + 1)]
    for i in range(n - 1):
        arr.append(arr[-1] + 1)    

    reqs = []

    for i in range(q):
        #print(i)
        act = random.randint(0, 1)
        if (act == 0):
            l = random.randint(0, n - 1)
            r = random.randint(0, n - 1)
            if (l > r):
                l, r = r, l
            d = random.randint(-maxd, maxd)
            reqs.append([0, l, r, d])
        else:
            l = random.randint(0, n - 1)
            r = random.randint(0, n - 1)
            if (l > r):
                l, r = r, l
            reqs.append([1, l, r])

    write_test(arr, reqs)       


def gen_test_with_big_requests(n, q):
    arr = []
    for i in range(n):
        arr.append(random.randint(-nowma, nowma))

    tmp = random.randint(10, 100)

    for i in range(tmp):
        l = random.randint(n // tmp, n)
        pos = random.randint(0, n - l)
        arr[pos] = random.randint(-maxa, maxa - l + 1)
        for j in range(1, l):
            arr[pos + j] = arr[pos + j - 1] + 1
        
    bdv = 1
    while (bdv * 2 <= n):
        bdv *= 2

    reqs = []

    for i in range(q):
        #print(i)
        act = random.randint(0, 1)
        if (act == 0):
            lr = bdv + random.randint(-2, 2)
            if (lr > n):
                lr = n;
            l = random.randint(0, n - lr)
            r = l + lr - 1
            
            d = random.randint(-maxd, maxd)
            reqs.append([0, l, r, d])
        else:
            lr = bdv + random.randint(-2, 2)
            if (lr > n):
                lr = n;
            l = random.randint(0, n - lr)
            r = l + lr - 1

            reqs.append([1, l, r])

    write_test(arr, reqs)       


def gen_test_with_many_joining(n, q):
    nowmaxd = 1000
    arr = [random.randint(-maxa + q * nowmaxd, maxa - n + 1 - q * nowmaxd)]
    for i in range(n - 1):
        arr.append(arr[-1] + 1)    

    reqs = []

    scanline = []

    for i in range(q):
        #print(i)
        act = random.randint(0, 1)
        if (act == 0):
            l = random.randint(0, n - 1)
            r = random.randint(0, n - 1)
            if (l > r):
                l, r = r, l
            d = random.randint(-nowmaxd, nowmaxd)
            reqs.append([0, l, r, d])
            scanline.append([l, -d])
            scanline.append([r + 1, d])
        else:
            l = random.randint(0, n - 1)
            r = random.randint(0, n - 1)
            if (l > r):
                l, r = r, l
            reqs.append([1, l, r])

    reqs.reverse()
    scanline.sort()
    
    c = 0
    bal = 0
    for i in range(n):
        while (c < len(scanline) and scanline[c][0] == i):
            bal += scanline[c][1]
            c += 1
        arr[i] += bal

    write_test(arr, reqs)       

write_test([2, 3, 4, 3, 4, 4], [[1, 0, 5], [0, 5, 5, 1], [1, 1, 5], [0, 3, 5, 2], [1, 0, 4]])

write_test([1], [])

write_test([123], [[1, 0, 0], [0, 0, 0, -123], [1, 0, 0], [0, 0, 0, -123], [1, 0, 0]])

for i in range(10):
    n = maxn // 10 * (i + 1)
    q = maxq

    nowma = 10
    nowmd = 1

    gen_random_test(n, q, nowma, nowmd)

for i in range(5):
    n = maxn // 2 + maxn // 2 // 5 * (i + 1)
    q = maxq

    gen_test_with_full_length_ap(n, q)


for i in range(5):
    n = maxn - random.randint(0, 12345)
    q = maxq

    gen_test_with_big_requests(n, q)

for i in range(5):
    n = maxn - random.randint(0, 12345)
    q = maxq

    gen_test_with_many_joining(n, q)

write_test([0, 1, 2], [[0, 1, 1, 10 ** 9], [0, 1, 1, 10 ** 9], [0, 1, 1, 10 ** 9], [0, 1, 1, 10 ** 9], [0, 1, 1, 294967296], [1, 0, 2]])

arr = [i for i in range(maxn)]
reqs = []

c = 0

while (c < maxq):
    tmp = []
    bal = 2 ** 32
    while (bal > 0):
        tmp.append(random.randint(min(maxd / 2, bal), min(maxd, bal)))
        bal -= tmp[-1]
        #print(bal)
    if (c + len(tmp) + 1 < maxq):
        l = random.randint(0, maxn - 1)
        r = random.randint(0, maxn - 1)
        if (l > r):
            l, r = r, l
        for num in tmp:
            reqs.append([0, l, r, num])
        l = random.randint(0, maxn - 1)
        r = random.randint(0, maxn - 1)
        if (l > r):
            l, r = r, l        
        reqs.append([1, l, r])
        c += len(tmp) + 1
    else:
        break
            
if (len(reqs) < maxq):
    reqs.append([1, 0, maxn - 1])

write_test(arr, reqs)