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

public class TestGen {
	public static void main(String[] args) {
		new TestGen().run();
	}

	BufferedReader br;
	StringTokenizer in;
	PrintWriter out;

	public String nextToken() throws IOException {
		while (in == null || !in.hasMoreTokens()) {
			in = new StringTokenizer(br.readLine());
		}
		return in.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	int tNumber;

	Random rnd;

	void print(int n, int[] a, int m, int[][] b) throws IOException {
		if (tNumber < 10) {
			out = new PrintWriter("0" + tNumber);
		} else {
			out = new PrintWriter("" + tNumber);
		}
		tNumber++;
		out.println(n);
		for (int i = 0; i < n; i++) {
			out.print((a[i] + 1) + " ");
		}
		out.println();
		out.println(m);
		for (int i = 0; i < m; i++) {
			out.println((b[i][0] + 1) + " " + (b[i][1] + 1));
		}
		out.close();
	}

	int[][] genquery(int n, int m, int val, int[] a) {
		int[][] b = new int[m][2];
		for (int i = 1; i < m; i++) {
			int len = rnd.nextInt(n);
			b[i][0] = rnd.nextInt(n - len);
			b[i][1] = len + b[i][0];
		}
		for (int i = 0; i < 3; i++) {
			b[i][0] = rnd.nextInt(n - 5);
			b[i][1] = b[i][0] + 2;
			a[b[i][0]] = a[b[i][0] + 1] = a[b[i][0] + 2] = val;
		}
		b[m - 1][0] = 0;
		b[m - 1][1] = n - 1;
		return b;
	}

	int[][] genquery(int n, int m) {
		int[][] b = new int[m][2];
		for (int i = 1; i < m; i++) {
			int len = rnd.nextInt(n);
			b[i][0] = rnd.nextInt(n - len);
			b[i][1] = len + b[i][0];
		}
		return b;
	}

	void gen1(int n, int m, int val) throws IOException {
		ArrayList<Integer> c = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			c.add(i % val);
		}
		Collections.shuffle(c);
		int t = 0;
		int[] a = new int[n];
		for (int i : c) {
			a[t++] = i;
		}
		int[][] b = genquery(n, m, rnd.nextInt(val), a);
		print(n, a, m, b);
	}

	void gen2(int n, int m, int val) throws IOException {
		int[] a = new int[n];
		val = rnd.nextInt(val);
		for (int i = 0; i < n; i++) {
			a[i] = val * (i % 2);
		}
		print(n, a, m, genquery(n, m, val, a));
	}

	void gen3(int n, int m, int val) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = 0;
		}
		print(n, a, m, genquery(n, m, rnd.nextInt(val), a));
	}

	void gen4(int n, int m, int val) throws IOException {
		int[] a = new int[n];
		Arrays.fill(a, -1);
		int left = n;
		for (int i = 0; i < n / 5; i++) {
			int hp = rnd.nextInt(n);
			while (a[hp] != -1) {
				hp = rnd.nextInt(n);
			}
			a[hp] = rnd.nextInt(val);
			left--;
		}
		while (left > 0) {
			int need = (left + 1) / 2;
			int f1 = (need + 1) / 2;
			int f2 = need - f1;
			int p1 = rnd.nextInt(val);
			int p2 = rnd.nextInt(val);
			while (f1 > 0) {
				int hp = rnd.nextInt(n);
				while (a[hp] != -1) {
					hp = rnd.nextInt(n);
				}
				a[hp] = p1;
				f1--;
			}
			while (f2 > 0) {
				int hp = rnd.nextInt(n);
				while (a[hp] != -1) {
					hp = rnd.nextInt(n);
				}
				a[hp] = p2;
				f2--;
			}
			left -= need;
		}
		print(n, a, m, genquery(n, m, rnd.nextInt(val), a));
	}

	int genrandom(int val) {
		return 9 * val / 10 + rnd.nextInt(val) % (val / 12);

	}

	void gen6(int n, int m, int val) throws IOException {
		int[] a = new int[n];
		int len = (int) (Math.sqrt(n) + 100);
		int left = n;
		int k = n / len / 2;
		Arrays.fill(a, -1);
		for (int i = 0; i < k; i++) {
			int num = rnd.nextInt(val);
			int help = len;
			while (help > 0) {
				int tek = rnd.nextInt(n);
				if (a[tek] == -1) {
					a[tek] = num;
					help--;
				}
			}
			left -= len;
		}
		len = (int) (Math.sqrt(n) - 100);
		k = left / len / 2;
		for (int i = 0; i < k; i++) {
			int num = rnd.nextInt(val);
			int help = len;
			while (help > 0) {
				int tek = rnd.nextInt(n);
				if (a[tek] == -1) {
					a[tek] = num;
					help--;
				}
			}
			left -= len;
		}
		for (int i = 0; i < n; i++) {
			if (a[i] == -1) {
				a[i] = rnd.nextInt(val);
			}
		}
		print(n, a, m, genquery(n, m, rnd.nextInt(val), a));

	}

	void runbig(int n, int m, int val) throws IOException {
		gen2(genrandom(n), genrandom(m), val);
		gen3(genrandom(n), genrandom(m), val);
		for (int i = 0; i < 2; i++) {
			gen1(genrandom(n), genrandom(m), val);
		}
		for (int i = 0; i < 6; i++) {
			gen4(genrandom(n), genrandom(m), val);
		}
		if (n > 20000 && val > 20000) {
			for (int i = 0; i < 9; i++) {
				gen6(genrandom(n), genrandom(m), val);
			}
		}
	}

	void gen5() throws IOException {
		int n = 100000;
		int m = 100000;
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = rnd.nextInt(1000000000);
		}
		int[][] b = new int[m][2];
		for (int i = 0; i < m; i++) {
			b[i][0] = 0;
			b[i][1] = m - 1;
		}
		print(n, a, m, b);
	}

	public void solve() throws IOException {
		tNumber = 1;
		rnd = new Random(31);
		runbig(100, 100, 1000000000);
		runbig(3000, 3000, 1000000000);
		runbig(100000, 100000, 5);
		runbig(100000, 100000, 1000000000);
		gen5();
	}

	public void run() {
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
}