import random
import os
import shutil

num_of_subtasks = 3

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

for i in range(num_of_subtasks):
    name = "subtask" + str(i + 1)
    try:
        os.makedirs('../tests/' + name)
    except OSError:
        pass

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

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

descf = open("../tests.desc", "w")

random.seed(239)

test_number = 1

def write_test(n, k, tickets, reqs, subtask, desc=""):
    global test_number
    name = "0" * (2 - len(str(test_number))) + str(test_number)

    adr = ""

    if (subtask == 0):
        adr = "../preliminary/" + name
    else:
        adr = "../tests/subtask" + str(subtask) + "/" + name

    outp = open(adr, "w")

    descf.write(adr + "   n = " + str(n) + ", m = " + str(len(tickets)) + ", k = " + str(k) + ", q = " + str(len(reqs)) + " " + desc + "\n")

    outp.write(str(n) + " " + str(len(tickets)) + " " + str(k) + "\n")

    for t in tickets:
        outp.write(str(t[0] + 1) + " " + str(t[1] + 1) + " " + str(t[2] + 1) + "\n")

    outp.write(str(len(reqs)) + "\n")
    for r in reqs:
        outp.write(str(r[0] + 1) + " " + str(r[1] + 1) + "\n")

    if (subtask == 0):
        print("Preliminary test #" + str(test_number) + " has been generated")
    else:
        print("Test #" + str(test_number) + " has been generated")

    test_number += 1
    outp.close()



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

test_number = 1

def gen_random_test(n, m, k, q, subtask):
    tickets = [[] for i in range(k)]
    reqs = []

    for i in range(m - k):
        pl = random.randint(0, k - 1)
        s = random.randint(0, n - 1)
        t = random.randint(0, n - 2)
        if (t >= s):
            t += 1
        if (s > t):
            s, t = t, s
        tickets[pl].append([s, t])

    allt = []
    for i in range(k):
        if (not len(tickets[i])):
            continue

        tickets[i].sort()
        allt.append(tickets[i][0] + [i])
        for j in range(1, len(tickets[i])):
            if (allt[-1][1] <= tickets[i][j][0]):
                allt.append(tickets[i][j] + [i])
            else:
                allt[-1][1] = max(allt[-1][1], tickets[i][j][1])

    random.shuffle(allt)
    
    for i in range(q):
        l = random.randint(n / 2, n - 1)
        s = random.randint(0, n - 1 - l)
        t = s + l
        reqs.append([s, t])

    write_test(n, k, allt, reqs, subtask, "random test")
            

def gen_test_with_little_free_space(n, m, k, q, maxl, subtask):
    tickets = [[] for i in range(k)]
    reqs = []

    for i in range(m - k):
        pl = random.randint(0, k - 1)
        l = random.randint(1, min(maxl, n - 1))
        s = random.randint(0, n - 1 - l)
        t = s + l
        tickets[pl].append([s, t])

    allt = []
    for i in range(k):
        #if (not len(tickets[i])):
        #    continue

        tickets[i].sort()
        nowarr = []
        if (len(tickets[i])):
            nowarr.append(tickets[i][0])
            for j in range(1, len(tickets[i])):
                if (nowarr[-1][1] < tickets[i][j][0]):
                    nowarr.append(tickets[i][j] + [i])
                else:
                    nowarr[-1][1] = max(nowarr[-1][1], tickets[i][j][1])

        prev = 0
        for p in nowarr:
            if (p[0] > prev):
                allt.append([prev, p[0], i])
            prev = p[1]
        if (prev < n - 1):
            allt.append([prev, n - 1, i])
    
    random.shuffle(allt)
    
    for i in range(q):
        l = random.randint(1, max(n / 5, 1))
        s = random.randint(0, n - 1 - l)
        t = s + l
        reqs.append([s, t])

    write_test(n, k, allt, reqs, subtask, "random test with little segments of free space")


def gen_test_with_big_answer(n, m, k, q, maxl, nump, skip, flag, subtask):
    tickets = [[] for i in range(k)]
    reqs = []

    pos = 0

    while (pos < n - 1):
        best = 0
        for i in range(nump):
            pl = random.randint(0, k - 1)
            s = random.randint(max(0, pos - 3), pos)
            t = random.randint(min(n - 1, pos + maxl // 2), min(n - 1, pos + maxl))
            best = max(best, t)
            tickets[pl].append([s, t])

        pos = best
        #print(pos)
        if (skip and pos < n - 1 and random.randint(0, skip) == 0):
            pos += random.randint(1, min(n - 1 - pos, maxl // 2))


    allt = []
    for i in range(k):
        #if (not len(tickets[i])):
        #    continue

        tickets[i].sort()
        nowarr = []
        if (len(tickets[i])):
            nowarr.append(tickets[i][0])
            for j in range(1, len(tickets[i])):
                if (nowarr[-1][1] < tickets[i][j][0]):
                    nowarr.append(tickets[i][j] + [i])
                else:
                    nowarr[-1][1] = max(nowarr[-1][1], tickets[i][j][1])

        prev = 0
        for p in nowarr:
            if (p[0] > prev):
                allt.append([prev, p[0], i])
            prev = p[1]
        if (prev < n - 1):
            allt.append([prev, n - 1, i])
    
    random.shuffle(allt)
    
    start = 0
    if (flag):
        reqs.append([0, n - 1])
        start = 1

    for i in range(start, q):
        l = random.randint(1, n - 1)
        s = random.randint(0, n - 1 - l)
        t = s + l
        reqs.append([s, t])

    desc = "there are not more than " + str(nump) + " parallel segments of free space at any time"
    if (not skip):
        desc += ", way from begin to end exist"
    
    write_test(n, k, allt, reqs, subtask, desc)


write_test(2, 1, [], [[0, 1]], 1, "handmade test")
write_test(2, 1, [[0, 1, 0]], [[0, 1]], 1, "handmade test")
write_test(5, 4, [[0, 2, 0], [2, 4, 1], [0, 4, 2], [2, 3, 3], [3, 4, 0]], [[0, 2]], 1, "handmade test")
write_test(8, 3, [[0, 1, 0], [5, 7, 0], [3, 6, 1], [0, 3, 2], [6, 7, 2]], [[0, 7]], 1, "handmade test")
gen_random_test(100, 100, 20, 1, 1)
gen_test_with_little_free_space(100, 100, 50, 1, 2, 1)
gen_test_with_little_free_space(100, 100, 50, 1, 5, 1)
gen_test_with_little_free_space(100, 100, 50, 1, 10, 1)
gen_test_with_big_answer(100, 100, 90, 1, 15, 1, 0, 0, 1)
gen_test_with_big_answer(100, 100, 50, 1, 20, 3, 3, 0, 1)
gen_test_with_big_answer(100, 100, 50, 1, 20, 3, 0, 1, 1)
gen_test_with_big_answer(100, 100, 50, 1, 5, 1, 0, 1, 1)
gen_test_with_big_answer(100, 100, 50, 1, 5, 1, 25, 0, 1)

# (n, m, k, q, maxl, nump, skip, flag, subtask)


gen_random_test(200000, 200000, 50000, 1, 2)
gen_test_with_little_free_space(200000, 200000, 100000, 1, 2, 2)
gen_test_with_little_free_space(200000, 200000, 100000, 1, 5, 2)
gen_test_with_little_free_space(200000, 200000, 100000, 1, 10, 2)
gen_test_with_little_free_space(200000, 200000, 100000, 1, 50, 2)
gen_test_with_big_answer(200000, 200000, 100000, 1, 10, 1, 0, 0, 2)
gen_test_with_big_answer(200000, 200000, 100000, 1, 100, 10, 0, 0, 2)
gen_test_with_big_answer(200000, 200000, 100000, 1, 100, 10, 0, 1, 2)
gen_test_with_big_answer(200000, 200000, 100, 1, 3, 2, 0, 1, 2)
gen_test_with_big_answer(200000, 200000, 100000, 1, 5, 1, 0, 1, 2)
gen_test_with_big_answer(200000, 200000, 100000, 1, 5, 1, 50000, 0, 2)


gen_random_test(200000, 200000, 10000, 200000, 3)
gen_random_test(200000, 200000, 1000, 200000, 3)
gen_test_with_little_free_space(200000, 200000, 50000, 200000, 1000, 3)
gen_test_with_little_free_space(200000, 200000, 100000, 200000, 5000, 3)
gen_test_with_big_answer(200000, 200000, 100000, 200000, 10, 4, 1000, 1, 3)
gen_test_with_big_answer(200000, 200000, 100000, 200000, 50, 20, 1000, 1, 3)
gen_test_with_big_answer(200000, 200000, 100000, 200000, 5, 2, 10000, 1, 3)
gen_test_with_big_answer(200000, 200000, 100000, 200000, 5, 2, 0, 1, 3)
gen_test_with_big_answer(200000, 200000, 100000, 200000, 100, 10, 1000, 1, 3)
gen_test_with_big_answer(200000, 200000, 100000, 200000, 1000, 100, 1000, 1, 3)
gen_test_with_big_answer(200000, 200000, 100000, 200000, 20000, 9000, 0, 1, 3)
gen_random_test(200000, 200000, 50000, 200000, 3)
