from os import *
from io import *
import random
#works about 1 min

MAXN = 100000

def test(testNo, i):
	print(str(testNo));
	if not (path.exists("../tests")):
		mkdir("../tests")
	tst = open("../tests/%d%d" % divmod(testNo, 10), "w")
	tst.write(str(n[i]) + "\n");
	for j in range(n[i] - 1):
		tst.write(str(perm[i][j]) + " ");
	tst.write(str(perm[i][n[i] - 1]) + "\n");
	tst.write(str(k[i]) + "\n");
	for j in range(k[i] - 1):
		tst.write(str(sec[i][j]) + " ");
	tst.write(str(sec[i][k[i] - 1]) + "\n");
	if (k[i] != n[i]):
		for j in range(n[i] - k[i] - 1):
			tst.write(str(sec[i][j + k[i]]) + " ");
		tst.write(str(sec[i][n[i] - 1]) + "\n");
	else:
		tst.write("\n");	
	tst.close()


def genK(testNo, kk):

	print(str(testNo));
	if not (path.exists("../tests")):
		mkdir("../tests")
	tst = open("../tests/%d%d" % divmod(testNo, 10), "w")
	tst.write("10\n");
	for j in range(9):
		tst.write(str(randPerm[j]) + " ");
	tst.write(str(randPerm[9]) + "\n");
	tst.write(str(kk) + "\n");
	for j in range(kk - 1):
		tst.write(str(randSec[j]) + " ");
	tst.write(str(randSec[kk - 1]) + "\n");
	if (kk != 10):
		for j in range(10 - kk - 1):
			tst.write(str(randSec[j + kk]) + " ");
		tst.write(str(randSec[9]) + "\n");
	else:
		tst.write("\n");	
	tst.close()

def genMost(testNo):

	print(str(testNo));
	if not (path.exists("../tests")):
		mkdir("../tests")
	tst = open("../tests/%d%d" % divmod(testNo, 10), "w")
	tst.write(str(MAXN) + "\n");
	for j in range(MAXN - 1):
		tst.write(str(j + 1) + " ");
	tst.write(str(MAXN) + "\n1\n100000\n");
	
	for j in range(MAXN - 2):
		tst.write(str(MAXN-1-j) + " ");
	tst.write("1\n");
	tst.close();
	
def genSmart(testNo):

	print(str(testNo));
	if not (path.exists("../tests")):
		mkdir("../tests")
	tst = open("../tests/%d%d" % divmod(testNo, 10), "w")
	tst.write(str(MAXN) + "\n");
	for j in range(MAXN - 1):
		tst.write(str(j + 1) + " ");
	tst.write(str(MAXN) + "\n100000\n");
	
	for j in range(MAXN - 1):
		tst.write(str(MAXN-j) + " ");
	tst.write("1\n\n");
	tst.close();

def genRandom(testNo, kk):
	print(str(testNo));
	if not (path.exists("../tests")):
		mkdir("../tests")
	tst = open("../tests/%d%d" % divmod(testNo, 10), "w")
	tst.write(str(MAXN) + "\n");
	for j in range(MAXN - 1):
		tst.write(str(p[j]) + " ");
	tst.write(str(p[MAXN - 1]) + "\n");
	tst.write(str(kk) + "\n");
	for j in range(kk - 1):
		tst.write(str(s[j]) + " ");
	tst.write(str(s[kk - 1]) + "\n");
	if (kk != MAXN):
		for j in range(MAXN - kk - 1):
			tst.write(str(s[j + kk]) + " ");
		tst.write(str(s[MAXN - 1]) + "\n");	
	else:
		tst.write("\n");
	tst.close()
	

n = [4, 4, 4, 4, 4, 4, 1, 2]
k = [2, 2, 1, 2, 3, 4, 1, 1]
perm = [[3, 1, 4, 2], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1], [2, 1]]
sec = [[2, 3, 1, 4], [1, 3, 4, 2], [4, 3, 2, 1], [4, 3, 2, 1], [4, 3, 2, 1], [4, 3, 2, 1], [1], [1, 2]]


random.seed(31310031);
testNo = 0
for i in range(8):
	testNo = testNo + 1
	test(testNo, i);

randPerm = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for j in range(100):
	x = random.randint(0, 9);
	y = random.randint(0, 9);
	z = randPerm[x];
	randPerm[x] = randPerm[y];
	randPerm[y] = z;

randSec = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for j in range(100):
	x = random.randint(0, 9);
	y = random.randint(0, 9);
	z = randSec[x];
	randSec[x] = randSec[y];
	randSec[y] = z;
	
#different k
for i in range(10):
	testNo = testNo + 1
	genK(testNo, i + 1);

#most
testNo = testNo + 1
genMost(testNo);

#smart
testNo = testNo + 1
genSmart(testNo);

p = []
s = []
for q in range(MAXN):
	s += [q + 1]
	p += [q + 1]

for i in range(11):
	testNo = testNo + 1
	for j in range(MAXN):
		x = random.randint(0, MAXN - 1);
		y = random.randint(0, MAXN - 1);
		z = p[x];
		p[x] = p[y];
		p[y] = z;
	for j in range(MAXN):
		x = random.randint(0, MAXN - 1);
		y = random.randint(0, MAXN - 1);
		z = s[x];
		s[x] = s[y];
		s[y] = z;

	
	genRandom(testNo, random.randint(0, MAXN - 1));



