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

public class Gen {

	static int done = 0;

	static public class Pair {
		int x, y;

		Pair(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	};

	static ArrayList<Pair> data = new ArrayList<Pair>();

	static final int MAXH = 1000;
	static final int MAXW = MAXH;
	static final int MAX_COUNT_LIGHTS = (int) 1e5;

	static final Random rand = new Random(556668949239L);

	static void print(int h, int w) throws IOException {
		done++;
		System.err.println(done);
		PrintWriter out;
		if (done < 10)
			out = new PrintWriter("../tests/0" + String.valueOf(done));
		else
			out = new PrintWriter("../tests/" + String.valueOf(done));

		out.println(h + " " + w + " " + data.size());
		for (int i = 0; i < data.size(); i++) {
			out.println(data.get(i).x + " " + data.get(i).y);
		}
		data.clear();
		out.close();
	}

	static void print(int h, int w, int cnt) throws IOException {
		done++;
		System.err.println(done);
		PrintWriter out;
		if (done < 10)
			out = new PrintWriter("../tests/0" + String.valueOf(done));
		else
			out = new PrintWriter("../tests/" + String.valueOf(done));

		cnt = Math.min(data.size(), cnt);
		out.println(h + " " + w + " " + cnt);
		for (int i = 0; i < cnt; i++) {
			out.println(data.get(i).x + " " + data.get(i).y);
		}
		data.clear();
		out.close();
	}

	static void addLight(int x, int y) throws IOException {
		data.add(new Pair(x + 1, y + 1));
	}

	static void genFill(int h, int w) throws IOException {
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				addLight(i, j);
		Collections.shuffle(data, rand);
		print(h, w);
	}

	static void genRandom(int h, int w, int cnt) throws IOException {
		for (int i = 0; i < cnt; i++)
			addLight(rand.nextInt(h), rand.nextInt(w));
		print(h, w);
	}

	static void genInv(int h, int w, int cnt) throws IOException {
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				addLight(i, j);
		Collections.shuffle(data, rand);
		print(h, w, h * w - cnt);
	}

	static void genSpecial1(int h, int w, int r) throws IOException {
		for (int i = 0; i < h; i += 2 * r)
			for (int j = 0; j < w; j += 2 * r)
				addLight(i, j);
		Collections.shuffle(data, rand);
	}

	static void genSpecial2(int h, int w, int r) throws IOException {
		for (int i = r; i < h; i += 2 * r)
			for (int j = r; j < w; j += 2 * r)
				addLight(i, j);
		Collections.shuffle(data, rand);
	}

	static void genSpecial(int h, int w, int r) throws IOException {
		genSpecial1(h, w, r);
		genSpecial2(h, w, r);

	}

	static void genSimple() throws IOException {
		data.add(new Pair(2, 1));
		data.add(new Pair(2, 3));
		print(3, 3);
	}

	public static void main(String[] args) throws IOException {
		File dir = new File("../tests");
		if (!dir.exists())
			dir.mkdir();
		done = 0;
		genSimple();

		// Small test case
		genFill(1, 1);
		genInv(1, 1, 1);

		addLight(0, 0);
		print(3, 3);

        addLight(0, 0);
        addLight(5, 0);
        addLight(0, 5);
        addLight(5, 5);
        print(6, 6);

		genInv(3, 3, 1);
		genRandom(10, 10, 5);
		genFill(5, 5);

		genSpecial(4, 4, 1);
		print(4, 4);

		genSpecial(4, 4, 1);
		print(4, 4, 10);

		addLight(4, 4);
		print(9, 9);

		genSpecial1(15, 15, 2);
		for (int i = 0; i < 5; i++)
			addLight(rand.nextInt(15), rand.nextInt(15));
		print(15, 15);

		// Middle1 test case

		genFill(100, 100);
		genRandom(100, 100, 500);
		genInv(100, 100, 2000);

		genSpecial(100, 100, 10);
		print(100, 100);

		genSpecial(100, 100, 15);
		print(100, 100, 100);

		genSpecial1(100, 100, 20);
		for (int i = 0; i < 5; i++)
			addLight(rand.nextInt(100), rand.nextInt(100));
		print(500, 500);

		genSpecial2(100, 100, 30);
		print(100, 100);

		// Middle2 test case
		genFill(200, 500);
		genRandom(500, 500, 5000);
		genInv(500, 500, 150000);

		genSpecial(500, 500, 10);
		print(500, 500);

		genSpecial(500, 500, 15);
		print(500, 500, 100);

		genSpecial1(500, 500, 200);
		for (int i = 0; i < 5; i++)
			addLight(rand.nextInt(500), rand.nextInt(250));
		print(500, 500);

		genSpecial2(500, 500, 200);
		print(500, 500);

		// Big test case
		addLight(0, 0);
		print(MAXH, MAXW);

		for (int i = 2; i < 6; i++)
			genRandom(rand.nextInt(i * 100) + 500, rand.nextInt(i * 100) + 500,
					rand.nextInt(MAX_COUNT_LIGHTS / 2) + MAX_COUNT_LIGHTS / 2);

		genSpecial1(MAXH, MAXW, 1000);
		for (int i = 0; i < 100; i++)
			addLight(rand.nextInt(MAXH), rand.nextInt(MAXW));
		print(MAXH, MAXW);

		for (int i = 0; i < 3; i++)
			genRandom(MAXH, MAXW, MAX_COUNT_LIGHTS);

		genSpecial(MAXH, MAXW, 100);
		for (int i = 0; i < 1000; i++)
			addLight(rand.nextInt(MAXH), rand.nextInt(MAXW));
		Collections.shuffle(data, rand);
		print(MAXH, MAXW, rand.nextInt(data.size() / 3) + data.size() / 2);

		genSpecial(MAXH, MAXW,
				MAXH / (int) (Math.sqrt(1.0 * MAX_COUNT_LIGHTS / 2)));
		print(MAXH, MAXW);

		for (int i = 0; i < 2; i++) {
			addLight(0, 0);
			addLight(0, MAXW - i - 1);
			addLight(MAXH - i - 1, 0);
			addLight(MAXH - i - 1, MAXW - i - 1);
			print(MAXH - i, MAXW - i);
		}
		genSpecial2(MAXH, MAXW, 100);
		for (int i = 0; i < 5000; i++)
			addLight(rand.nextInt(MAXH), rand.nextInt(MAXW));
		Collections.shuffle(data, rand);
		print(MAXH, MAXW, rand.nextInt(data.size() / 3) + data.size() / 2);

		genInv((int) (Math.sqrt(1.0 * MAX_COUNT_LIGHTS)),
				(int) (Math.sqrt(1.0 * MAX_COUNT_LIGHTS)), 1);
		return;
	}
}
