import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;

public class sorting_gen {

	public static void main(String[] args) throws IOException {
		Random rand = new Random(91234785);
		for (int test = 1; test <= 50; test++) {
			PrintWriter out = new PrintWriter((test < 10 ? "0" : "") + test);
			switch (test) {
			case 1:
				out.println("4 10");
				out.println("5 6 3 4");
				break;
			case 2:
				out.println("4 9");
				out.println("5 6 3 4");
				break;
			case 3:
			case 4:
			case 5: {
				int x = 2 + rand.nextInt(99999);
				if (test == 5) {
					x = 100000;
				}
				out.println(x + " " + (x + 1));
				int[] a = new int[x];
				for (int i = a.length - 1; i >= 0; i--) {
					if ((a.length - i) % 2 == 1) {
						a[i] = ((a.length - i + 1) / 2);
					} else {
						a[i] = (x - (a.length - i - 1) / 2);
					}
				}
				for (int i = 0; i < a.length; i++) {
					if (i > 0) {
						out.print(" ");
					}
					out.print(a[i]);
				}
				out.println();
			}
				break;
			case 6:
			case 7:
			case 8: {
				int x = 2 + rand.nextInt(99999);
				if (test == 8) {
					x = 100000;
				}
				out.println(x + " " + x);
				int[] a = new int[x];
				for (int i = a.length - 1; i >= 0; i--) {
					if ((a.length - i) % 2 == 1) {
						a[i] = ((a.length - i + 1) / 2);
					} else {
						a[i] = (x - (a.length - i - 1) / 2);
					}
				}
				for (int i = 0; i < a.length; i++) {
					if (i > 0) {
						out.print(" ");
					}
					out.print(a[i]);
				}
				out.println();
			}
				break;
			case 9:
				out.println("2 1000000000");
				out.println("1 1000000000");
				break;
			case 10:
				out.println("2 1000000000");
				out.println("1000000000 1");
				break;
			case 11:
				out.println("2 1000000000");
				out.println("1 999999999");
				break;
			case 12:
				out.println("2 1000000000");
				out.println("999999999 1");
				break;
			case 13:
				out.println("100000 1000000000");
				for (int i = 0; i < 100000; i++) {
					if (i > 0) {
						out.print(" ");
					}
					out.print(1000000000 - 99999 + i);
				}
				out.println();
				break;
			case 14:
				out.println("100000 1000000000");
				for (int i = 0; i < 100000; i++) {
					if (i > 0) {
						out.print(" ");
					}
					out.print(1000000000 - i);
				}
				out.println();
				break;
			case 15:
			case 16:
			case 17:
			case 18:
			case 19:
				bigButSortedTest(out, rand);
				break;
			case 20:
			case 21:
			case 22:
			case 23:
			case 24:
				oneWrongSwapTest(out, rand);
				break;
			case 25:
				out.println("100000 1000000000");
				out.print(1000000000 - 99999);
				for (int i = 1; i < 100000; i++) {
					out.print(" " + (100000 - i));
				}
				out.println();
				break;
			case 26:
				out.println("100000 1000000000");
				out.print(1000000000 - 99998);
				for (int i = 1; i < 100000; i++) {
					out.print(" " + (100000 - i));
				}
				out.println();
				break;
			case 27:
				out.println("100000 1000000000");
				out.print(1000000000 - 99999);
				for (int i = 1; i < 100000; i++) {
					out.print(" " + i);
				}
				out.println();
				break;
			case 28:
				out.println("100000 1000000000");
				out.print(1000000000 - 99998);
				for (int i = 1; i < 100000; i++) {
					out.print(" " + i);
				}
				out.println();
				break;
			case 29:
			case 30:
			case 31:
			case 32:
			case 33:
				oneNoLongDistanceTest(out, rand);
				break;
			default:
				if (test < 45) {
					randomTest(out, rand, (test % 2) == 0);
				} else {
					randomTest(out, rand, (test % 2) == 0, 100000);
				}
				break;
			}
			out.close();
		}
	}

	private static void oneNoLongDistanceTest(PrintWriter out, Random rand) {
		int n = 50000 + rand.nextInt(50001);
		if (rand.nextBoolean()) {
			n = 100000;
		}
		int m = 100000000 + rand.nextInt(9 * 100000000 + 1);
		int[] a = new int[n];
		int k1 = rand.nextInt(n);
		int k2 = k1;
		while (k1 == k2) {
			k2 = rand.nextInt(n);
		}
		while (Math.abs(k1 - k2) < 30000) {
			k1 = rand.nextInt(n);
			k2 = k1;
			while (k1 == k2) {
				k2 = rand.nextInt(n);
			}
		}
		int tmp = Math.min(k1, k2);
		k2 = Math.max(k1, k2);
		k1 = tmp;
		int y = m / 10 + rand.nextInt(m - m / 5);
		y = Math.min(y, m - y);
		a[k1] = m - y + 1;
		a[k2] = y + 1;
		HashSet<Integer> hs = new HashSet<Integer>();
		hs.add(a[k1]);
		hs.add(a[k2]);
		for (int i = 0; i < a.length; i++) {
			if (i != k1 && i != k2) {
				a[i] = 1 + rand.nextInt(y - 1);
				while (hs.contains(a[i])) {
					a[i] = 1 + rand.nextInt(y - 1);
				}
				hs.add(a[i]);
			}
		}
		out.println(n + " " + (m - 1));
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				out.print(" ");
			}
			out.print(a[i]);
		}
		out.println();
	}

	private static void randomTest(PrintWriter out, Random rand, boolean yes,
			int... z) {
		int n = z.length == 0 ? 2 + rand.nextInt(99999) : z[0];
		int[] a = new int[n];
		int m = 0;
		HashSet<Integer> hs = new HashSet<Integer>();
		if (yes) {
			int max = 0;
			int maxSum = 1;
			for (int i = 0; i < a.length; i++) {
				while (true) {
					int x = 1 + rand.nextInt(1000000000 - max
							- (a.length - i - 1));
					if (!hs.contains(x)) {
						a[i] = x;
						hs.add(x);
						break;
					}
				}
				if (a[i] < max) {
					maxSum = Math.max(maxSum, max + a[i]);
				}
				max = Math.max(max, a[i]);
			}
			if (maxSum <= 1000000000) {
				m = maxSum + rand.nextInt(1000000001 - maxSum);
			} else {
				m = 1 + rand.nextInt(1000000000);
			}
		} else {
			int max = 0;
			int maxSum = 2;
			for (int i = 0; i < a.length; i++) {
				while (true) {
					int x = 1 + rand.nextInt(1000000000);
					if (!hs.contains(x)) {
						a[i] = x;
						hs.add(x);
						break;
					}
				}
				if (a[i] < max) {
					maxSum = Math.max(maxSum, max + a[i]);
				}
				max = Math.max(max, a[i]);
			}
			m = 1 + rand.nextInt(maxSum - 1);
		}
		m = Math.min(m, 1000000000);
		out.println(n + " " + m);
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				out.print(" ");
			}
			out.print(a[i]);
		}
		out.println();
	}

	private static void oneWrongSwapTest(PrintWriter out, Random rand) {
		int n = 50000 + rand.nextInt(50001);
		HashSet<Integer> hs = new HashSet<Integer>();
		while (hs.size() < n) {
			hs.add(1 + rand.nextInt(1000000000));
		}
		int[] a = new int[n];
		int k = 0;
		for (int i : hs) {
			a[k++] = i;
		}
		Arrays.sort(a);
		int j = rand.nextInt(n - 1);
		int m = Math.min(a[j] + a[j + 1] - 1, 1000000000);
		int tmp = a[j];
		a[j] = a[j + 1];
		a[j + 1] = tmp;
		out.println(n + " " + m);
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				out.print(" ");
			}
			out.print(a[i]);
		}
		out.println();
	}

	private static void bigButSortedTest(PrintWriter out, Random rand) {
		int n = 50000 + rand.nextInt(50001);
		int m = 1 + rand.nextInt(1000000000);
		HashSet<Integer> hs = new HashSet<Integer>();
		while (hs.size() < n) {
			hs.add(1 + rand.nextInt(1000000000));
		}
		int[] a = new int[n];
		int k = 0;
		for (int i : hs) {
			a[k++] = i;
		}
		Arrays.sort(a);
		out.println(n + " " + m);
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				out.print(" ");
			}
			out.print(a[i]);
		}
		out.println();
	}
}
