import java.io.*;
import java.util.*;

public class TestsGen {
	static int testcount = 0;

	static Random random = new Random(84673583);
	
	static int MAXN = 100000;
	static int MAXK = 100000;
	static int MAX = (int) 1e9;
	
	static void myAssert(boolean e, String s) {
		if (!e) {
			throw new Error("Assertion failure " + s);
		}
	}
	
	static void write(int[] a, int[] b, int[] c) throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		System.out.println("Generating test #" + testcount);
		myAssert(a.length == b.length, "Not equal size of arrays");
		out.println(a.length);
		for (int i = 0; i < a.length; i++) {
			out.println(a[i] + " " + b[i]);
		}
		out.println(c.length);
		for (int i = 0; i < c.length; i++) {
			if (i != 0) {
				out.print(" ");
			}
			out.print(c[i]);
		}
		out.println();
		out.close();
	}
	
	static void writeRand(int k, int n) throws IOException {
		int[] a = new int[k];
		int[] b = new int[k];
		int[] c = new int[n];
		for (int i = 0; i < k; i++) {
			a[i] = random.nextInt(MAXN - 1) + 2;
			b[i] = random.nextInt(MAX) + 1;
		}
		for (int i = 0; i < n; i++) {
			c[i] = random.nextInt(MAX) + 1;
		}
		write(a, b, c);
	}
	
	static void write1(int k, int MAX) throws IOException {
		int[] a = new int[k];
		int[] b = new int[k];
		int[] c = new int[1];
		int max = 0;
		for (int i = 0; i < k; i++) {
			a[i] = random.nextInt(MAXN - 1) + 2;
			b[i] = random.nextInt(MAX - 1) + 1;
			max = Math.max(max, b[i]);
		}
		c[0] = max + 1;
		write(a, b, c);
	}
	
	static void shuffle(int[] a) {
		for (int i = 0; i < a.length; i++) {
			int j = random.nextInt(i + 1);
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	
	static void shuffle(int[] a, int[] b) {
		for (int i = 0; i < a.length; i++) {
			int j = random.nextInt(i + 1);
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
			t = b[i];
			b[i] = b[j];
			b[j] = t;
		}
	}
	
	static void writeGood(int k, int n, int MAX) throws IOException {
		int[] a = new int[k];
		int[] b = new int[k];
		int[] c = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int t = Math.min(MAX / n * 3, MAX - sum - (n - i));
			c[i] = random.nextInt(t) + 1;
			sum += c[i];
		}
		Arrays.sort(c);
		
		int j = n - 1;
		for (int i = 0; i < k; i++) {
			a[i] = random.nextInt(MAXN - 1) + 2;
			long rest = 1L * (MAXN - 1) * (k - i - 1);
			if (j - a[i] + 1 > rest) {
				a[i] = (int) (j - rest + 1);
			}
			b[i] = sum + random.nextInt(MAX - sum + 1);
			for (int t = 0; t < a[i] - 1 && j > 0; t++) {
				sum -= c[j--];
			}
		}
		
		shuffle(a, b);
		shuffle(c);
		write(a, b, c);
	}

	static void writeGoodOnlyOne(int k, int n, int MAX) throws IOException {
		int[] a = new int[k];
		int[] b = new int[k];
		int[] c = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int t = Math.min(MAX / n * 3, MAX - sum - (n - i));
			c[i] = random.nextInt(t) + 1;
			sum += c[i];
		}
		Arrays.sort(c);
		
		int j = n - 1;
		for (int i = 0; i < k; i++) {
			a[i] = random.nextInt(Math.min(n, MAXN - 1)) + 2;
			long rest = 1L * (MAXN - 1) * (k - i - 1);
			if (j - a[i] + 1 > rest) {
				a[i] = (int) (j - rest + 1);
			}
			b[i] = sum;
			for (int t = 0; t < a[i] - 1 && j > 0; t++) {
				sum -= c[j--];
			}
		}
		
		shuffle(a, b);
		shuffle(c);
		write(a, b, c);
	}

	static void writeGood2(int n, int MAX) throws IOException {
		int k = n;
		int[] a = new int[k];
		int[] b = new int[k];
		int[] c = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int t = Math.min(MAX / n * 3, MAX - sum - (n - i));
			c[i] = random.nextInt(t) + 1;
			sum += c[i];
		}
		Arrays.sort(c);
		
		int j = n - 1;
		for (int i = 0; i < k; i++) {
			a[i] = 2;
			b[i] = sum + random.nextInt(MAX - sum + 1);
			for (int t = 0; t < a[i] - 1 && j > 0; t++) {
				sum -= c[j--];
			}
		}
		
		shuffle(a, b);
		shuffle(c);
		write(a, b, c);
	}

	static void writeGood3(int k, int n, int MAX) throws IOException {
		int[] a = new int[k];
		int[] b = new int[k];
		int[] c = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			c[i] = random.nextInt(MAX - sum - (n - i)) + 1;
			sum += c[i];
		}
		Arrays.sort(c);
		
		int j = n - 1;
		for (int i = 0; i < k; i++) {
			a[i] = random.nextInt(MAXN - 1) + 2;
			long rest = 1L * (MAXN - 1) * (k - i - 1);
			if (j - a[i] + 1 > rest) {
				a[i] = (int) (j - rest + 1);
			}
			b[i] = sum + random.nextInt(MAX - sum + 1);
			for (int t = 0; t < a[i] - 1 && j > 0; t++) {
				sum -= c[j--];
			}
		}
		
		shuffle(a, b);
		shuffle(c);
		write(a, b, c);
	}

	static void writeAlmostYES(int k, int n, int MAX) throws IOException {
		int[] a = new int[k];
		int[] b = new int[k];
		int[] c = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			c[i] = random.nextInt(MAX - sum - (n - i)) + 1;
			sum += c[i];
		}
		Arrays.sort(c);
		sum--;
		int j = n - 1;
		for (int i = 0; i < k; i++) {
			a[i] = random.nextInt(MAXN - 1) + 2;
			long rest = 1L * (MAXN - 1) * (k - i - 1);
			if (j - a[i] + 1 > rest) {
				a[i] = (int) (j - rest + 1);
			}
			b[i] = Math.max(sum, 1);
			for (int t = 0; t < a[i] - 1 && j > 0; t++) {
				sum -= c[j--];
			}
		}
		
		shuffle(a, b);
		shuffle(c);
		write(a, b, c);
	}

	public static void main(String[] args) throws IOException {
		while (new File(String.format("%02d.t", testcount + 1)).exists()) {
			testcount++;
		}
		for (int i = 0; i < 4; i++) {
			writeGood2(random.nextInt(10) + 1, 100);
			writeGood(random.nextInt(10) + 1, random.nextInt(10) + 1, 100);
			writeGoodOnlyOne(random.nextInt(10) + 1, random.nextInt(10) + 1, 100);
			writeAlmostYES(random.nextInt(10) + 1, random.nextInt(10) + 1, 100);
		}
		write1(10, 100);
		for (int i = 0; i < 3; i++) {
			writeGood2(random.nextInt(1000) + 1, MAX);
			writeGood(random.nextInt(1000) + 1, random.nextInt(1000) + 1, MAX);
			writeGoodOnlyOne(random.nextInt(1000) + 1, random.nextInt(1000) + 1, MAX);
			writeAlmostYES(random.nextInt(1000) + 1, random.nextInt(1000) + 1, MAX);
		}
		write1(1000, 1000);
		for (int i = 0; i < 3; i++) {
			writeGood3(random.nextInt(1000) + 1, random.nextInt(MAXK) + 1, MAX);
		}
		write1(MAXK, MAX);
		writeAlmostYES(10, 10, 1000);
		writeAlmostYES(10, 1000, 10000);
		writeAlmostYES(MAXK, MAXN, MAX);
		writeGoodOnlyOne(MAXK, MAXN, MAX);
		writeGoodOnlyOne(MAXK, MAXN, MAX);
		writeGood(MAXK, MAXN, MAX);
		writeGood(MAXK, MAXN, MAX);
		writeGood2(MAXK, MAX);
		writeGood2(MAXK, MAX);
		writeGood3(MAXK, MAXN, MAX);
		writeGood3(MAXK, MAXN, MAX);
	}

}
