from random import *
from os import path, mkdir

dir = '../tests'
test = 0
seed('ololo')

def printTest(a):
    #a[0] - n, m
    #a[1] - a
    #a[2] -l1, r1
    #a[3] - l2, r2
    global test
    if not (path.exists(dir)):
        mkdir(dir)
    test += 1
    print(test)
    ouf = open(dir + "/%02d" % test, 'w')
    print(' '.join(map(str, a[0])), file=ouf)
    print(' '.join(map(str, a[2])), file=ouf)
    print(' '.join(map(str, a[3])), file=ouf)
    print(' '.join(map(str, a[1])), file=ouf)
    ouf.close()

#win: 0 - Draw, 1 - Vasya, 2 - Petya
def genWithoutCommon(n, m, maxH, win):
    if win == 0: m += (m % 2)
    a = [randint(2, maxH) for _ in range(m)]
    a.sort()
    k = 0
    if win == 0:
        k = m // 2 - 1
    elif win == 1:
        k = randint(m // 2 + 1, m - 1)
    else:
        k = randint(0, m // 2 - 1)

    if a[k] == a[k + 1]:
        a[k + 1] += 1
    l1 = randint(1, a[0])
    r1 = randint(a[k], a[k + 1])
    l2 = randint(a[k] + 1, a[k + 1])
    r2 = randint(a[-1], maxH)

    for i in range(n - m):
        if bool(getrandbits(1)):
            a.append(randint(1, a[0]))
        else:
            a.append(randint(a[-1], maxH))
    shuffle(a)
    return([[n, m], a, [l1, r1], [l2, r2]])

def genWithCommon(n, m, maxH, win):
    common = randint(1, m)
    a = [randint(2, maxH - 1) for _ in range(common)]
    a.sort()

    v = (common + 1) // 2
    p = common // 2

    if win == 0:
        m += (m % 2)
        k = (m - len(a)) // 2
    elif win == 1:
        k = randint((m - len(a) + 1) // 2 + 1, m - len(a))
    else:
        k = randint(0, (m - len(a)) // 2)

    l1 = randint(1, a[0] - 1)
    r1 = randint(a[-1], maxH - 2)
    l2 = randint(l1 + 1, a[0])
    r2 = randint(r1 + 1, maxH)
    a.extend([randint(l1, l2 - 1) for _ in range(k)])
    a.extend([randint(r1 + 1, r2) for _ in range(m - common - k)])


    if win == 0:
        left1, right1 = 1, maxH
        left2, right2 = 1, maxH
    elif win == 1:
        left1, right1 = 1, r1 + 1
        left2, right2 = r2 + 1, maxH
    else:
        left1, right1 = 1, l1
        left2, right2 = l2, maxH

    for i in range(n - m):
        if bool(getrandbits(1)):
            a.append(randint(left1, right1))
        else:
            a.append(randint(left2, right2))

    shuffle(a)
    return([[n, m], a, [l1, r1], [l2, r2]])

printTest([[4, 3], [1, 2, 3, 4], [1, 2], [2, 4]])
printTest([[4, 4], [1, 2, 3, 4], [1, 4], [1, 4]])
printTest([[4, 4], [1, 2, 3, 4], [1, 2], [1, 4]])

printTest([[10, 1], [randint(1, 10) for i in range(10)], [1, 10], [1, 10]])
printTest([[10, 2], [randint(1, 10) for i in range(10)], [1, 10], [1, 10]])
printTest([[10, 3], [randint(1, 10) for i in range(10)], [1, 10], [1, 10]])
printTest([[10, 1], [randint(1, 10) for i in range(10)], [11, 20], [1, 10]])
printTest([[10, 2], [randint(1, 10) for i in range(10)], [11, 20], [1, 10]])
printTest([[10, 2], [randint(1, 10) for i in range(10)], [11, 20], [11, 20]])
printTest([[10, 3], [randint(1, 10) for i in range(10)], [11, 20], [11, 20]])
printTest([[10, 3], [randint(1, 10) for i in range(10)], [11, 20], [1, 10]])
printTest([[11, 3], [randint(1, 10) for i in range(10)] + [11], [11, 20], [1, 10]])
printTest([[12, 3], [randint(1, 10) for i in range(10)] + [11, 12], [11, 20], [1, 10]])
printTest([[12, 3], [randint(1, 10) for i in range(10)] + [11, 12], [11, 20], [1, 11]])

printTest(genWithoutCommon(10, 10, 1000, 1))
printTest(genWithoutCommon(50, 50, 5000, 0))
printTest(genWithoutCommon(100, 100, 5000, 2))

printTest(genWithCommon(200, 150, 10000, 0))
printTest(genWithCommon(400, 400, 10000, 2))
printTest(genWithCommon(500, 450, 100000, 1))

printTest(genWithoutCommon(10000, 5000, 1000000, 2))
printTest(genWithCommon(10000, 10000, 10000000, 0))
printTest(genWithCommon(100000, 50000, 10000000, 1))

printTest(genWithoutCommon(100000, 90000, 1000000000, 1))
printTest(genWithoutCommon(100000, 90000, 1000000000, 2))

for x in [10, 100, 1000]:
    for y in [x, x // 2, x - x // 10]:
        for z in [0, 1, 2]:
            printTest(genWithCommon(x, y, 10**9, z))

printTest(genWithCommon(100000, 80000, 1000000000, 0))
printTest(genWithCommon(100000, 90000, 1000000000, 1))
printTest(genWithCommon(100000, 90000, 1000000000, 2))


                                