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

public class TestsGen {
	static int testcount = 0;

	static Random random = new Random(25566);
	
	static String[] randomNames(int n) {
		String[] ans = new String[n];
		for (int i = 0; i < n; i++) {
			boolean fl;
			String s;
			do {
				s = "";
				for (int j = 0; j < 50; j++) {
					s += (char)('a' + random.nextInt(26));
				}
				fl = false;
				for (int j = 0; j < i; j++) {
					if (s.equals(ans[j])) {
						fl = true;
					}
				}
			} while (fl);
			ans[i] = s; 
		}
		return ans;
	}

	void write() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));

		out.close();
	}

	static void write1() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1000;
		int k = 999; 
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[random.nextInt(n)]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write3() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1000;
		int k = 900; 
		out.println(m + " " + k);
		int first = random.nextInt(n);
		out.println(names[first]);
		for (int i = 1; i < m; i++) {
			out.println(names[random.nextInt(n)]);
		}
		for (int i = 0; i < k; i++) {
			out.print(len[first]);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write2() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1000;
		int k = 999; 
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[0]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write4() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1000;
		int k = 0; 
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[random.nextInt(n)]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write5() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1;
		int k = 0; 
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[random.nextInt(n)]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write6() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1000;
		int k = 999; 
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[random.nextInt(n)]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write7() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1;
		int k = 0; 
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[random.nextInt(n)]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write8() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		ArrayList<Integer> num = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
			num.add(i);
		}
		int m = 1000;
		int k = 0; 
		Collections.shuffle(num);
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[num.get(i)]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write9() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1000;
		int k = 0;
		int num = random.nextInt(n);
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[num]);
		}
		for (int i = 0; i < k; i++) {
			out.print(0);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void write10() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = 1000;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m = 1000;
		int k = 500 - 1;
		int[] num = new int[m];
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			num[i] = random.nextInt(n);
			out.println(names[num[i]]);
		}
		int t = 0;
		for (int i = 0; i < k; i++) {
			out.print(t + num[2 * i]);
			t += num[2 * i];
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	static void writeRand() throws IOException {
		PrintWriter out = new PrintWriter(String.format("%02d", ++testcount));
		int n = random.nextInt(1000) + 1;
		String[] names = randomNames(n);
		int[] len = new int[n];
		out.println(n);
		for (int i = 0; i < n; i++) {
			len[i] = random.nextInt(30 * 60) + 1;
			out.println(names[i] + " " + len[i]);
		}
		int m, k;
		int[] a, b;
		boolean fl;
		do {
			fl = false;
			m = random.nextInt(1000) + 1;
			k = random.nextInt(m);
			a = new int[m];
			b = new int[k];
			int s = 0;
			for (int i = 0; i < m; i++) {
				a[i] = random.nextInt(n);
				s += len[a[i]];
			}
			for (int i = 0; i < k; i++) {
				b[i] = random.nextInt(s);
			}
			Arrays.sort(b);
			int j = 0;
			int curtime = 0;
			for (int i = 0; i < m; i++) {
				if (j < k && curtime + len[a[i]] > b[j]) {
					curtime = b[j];
					j++;
					if (i >= m - 1) {
						fl = true;
					}
				} else {
					curtime += len[a[i]];
				}
			}
/*			int t = 0;
			int j = 0;
			for (int i = 0; i < k; i++) {
				while (j < m && b[i] >= t + len[a[j]]) {
					t += len[a[j]];
					j++;
				}
				if (j >= m - 1) {
					fl = true;
				}
			}
*/		} while (fl);
		out.println(m + " " + k);
		for (int i = 0; i < m; i++) {
			out.println(names[a[i]]);
		}
		for (int i = 0; i < k; i++) {
			out.print(b[i]);
			if (i != k - 1) {
				out.print(" ");
			}
		}
		out.println();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		while (new File(String.format("%02d.t", testcount + 1)).exists()) {
			testcount++;
		}
		
		write1();
		write2();
		write3();
		write4();
		write5();
		write6();
		write7();
		write8();
		for (int i = 0; i < 3; i++) {
			write9();
		}
		write10();
		for (int i = 0; i < 20; i++) {
			writeRand();
		}
	}

}
