import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;


public class TestsGen {
	static Random rnd = new Random(3);
	final static double EPS = 1e-9;
	final static int P = 239017;
	final static int ITERATIONS_FOR_CHECK = 100;
	final static int MAXN = 100000;
	final static int MAXM = 100000;
	final static int MAXK = 100000000;
	static int tests = 0;
	
	static class Test {
		Point[] poly;
		Point[] queries;
		int index;
		int n;
		
		public Test(Point[] poly, int m) {
			this.poly = subarray(poly, 0, MAXN);
			this.n = this.poly.length;
			queries = genRandomQueries(poly, m, -MAXK, MAXK, -MAXK, MAXK);
			index = 1;
		}
		
		public Test(Point[] poly, Point[] queries) {
			this.poly = subarray(poly, 0, MAXN);
			this.n = this.poly.length;
			this.queries = subarray(queries, 0, MAXM);
			index = 1;
		}
		
		public Test(Point[] poly, Point[] queries, int index) {
			this(poly, queries);
			this.index = index;
		}
		
		Test rotate() {
			poly = TestsGen.rotate(poly, rnd.nextInt(MAXN));
			return this;
		}
		
		Test shuffleQueries() {
			for (int i = 1; i < queries.length; i++) {
				int pos = rnd.nextInt(i + 1);
				Point tmp = queries[i];
				queries[i] = queries[pos];
				queries[pos] = tmp;
			}
			return this;
		}
		
		void print() {
			tests++;
			PrintWriter out = null;
			try {
				out = new PrintWriter(String.format("%02d", tests));
			} catch (FileNotFoundException e) {
				System.err.print("[:(]");
			}
			out.println(poly.length + " " + index);
			for (Point p : poly) {
				out.println(p.x + " " + p.y);
			}
			out.println(queries.length);
			for (int i = 0; i < queries.length; i++) {
				out.println(queries[i].x + " " + queries[i].y + " ");
			}
			System.err.print("[" + tests + "]");
			out.close();
		}
	}
	
	static int signum(double a) {
		if (Math.abs(a) < EPS)
			return 0;
		return a < 0 ? -1 : 1;
	}
	
	static int orientation(Point a, Point b, Point c) { // sign of /_ABC
		double vect = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x); // BA x BC
		return signum(vect);
	}
	
	static Point[] ellipsoid(double X, double Y, int n) {
		Point[] p = new Point[n];
		for (int i = 0; i < n; i++) {
			int x = (int) (Math.sin(2 * Math.PI * i / n) * X);
			int y = (int) (Math.cos(2 * Math.PI * i / n) * Y);
			p[i] = new Point(x, y);
		}
		Point[] ch = convexHull(p);
		return ch;
	}
	
	static Point[] genRandomQueries(Point[] poly, int n, int MINX, int MAXX, int MINY, int MAXY) {
		Point[] res = new Point[n];
		for (int i = 0; i < n; i++) {
			while (true) {
				int x = rnd.nextInt(MAXX - MINX) + MINX;
				int y = rnd.nextInt(MAXY - MINY) + MINY;
				Point p = new Point(x, y);
				if (checkIfCannotBeInPolygon(poly, p)) {
					res[i] = p;
					break;
				}
			}
		}
		return res;
	}
	
	static boolean checkIfCannotBeInPolygon(Point[] p, Point q) {
		int n = p.length;
		for (int i = 0, it = 0; it < ITERATIONS_FOR_CHECK; it++, i += P) {
			int p1 = i % n;
			int p2 = (i + 1) % n;
			if (orientation(q, p[p1], p[p2]) == -1)
				return true;
		}
		return false;
	}

	static void shift(Point[] p, long x, long y) {
		for (Point q : p) {
			q.x += x;
			q.y += y;
		}
	}

	static Point[] rotate(Point[] p, int shift) {
		Point[] newP = new Point[p.length];
		for (int i = 0; i <p.length; i++) 
			newP[i] = p[(i + shift) % p.length];
		return newP;
	}
	
	static Point[] subarray (Point[] a, int left, int right) {
		if (left > right) {
			int tmp = right;
			right = left;
			left = tmp;
		}
		if (right > a.length)
			return a;
		Point[] newA = new Point[right - left];
		for (int i = 0; i < newA.length; i++) {
			newA[i] = a[i + left];
		}
		return newA;
	}
	
	static class Point implements Comparable<Point> {
		long x, y;
		
		public Point(long x, long y) {
			this.x = x;
			this.y = y;
		}
		
		@Override
		public String toString() {
			return "(" + x + ", " + y + ")";
		}

//		@Override
//		public int compareTo(Point o) {
//			return signum(y * o.x - x * o.y);
//		}		
//		
		@Override
		public int compareTo(Point o) {
			if (x == 0 && y == 0)
				return -1;
			if (o.x == 0 && o.y == 0)
				return 1;
			double angle1 = Math.atan2(y, x);
			double angle2 = Math.atan2(o.y, o.x);
			int res = signum(angle1 - angle2);			
			if (res == 0) {
				return Long.signum(x - o.x);
			}
			return res;
		}	
	}
	
	static Point[] convexHull(Point[] p) {
		int min = 0;
		int n = p.length;
		for (int i = 0; i < n; i++) {
			if (p[i].x < p[min].x || (p[i].x == p[min].x && p[i].y < p[min].y))
				min = i;
		}
		Point MIN = new Point(p[min].x, p[min].y);
		for (Point point : p) {
			point.x -= MIN.x;
			point.y -= MIN.y;
		}
		Arrays.sort(p);
		ArrayList<Point> stack = new ArrayList<Point>();
		stack.add(p[0]);
		stack.add(p[1]);
		for (int i = 2; i < n; i++) {
			while (stack.size() > 1) {
				Point a = stack.get(stack.size() - 2);
				Point b = stack.get(stack.size() - 1);
				Point c = p[i];
				double vect = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
				if (signum(vect) != 1)
					stack.remove(stack.size() - 1);
				else {
					break;
				}
			}
			stack.add(p[i]);
		}
		Point[] ans = new Point[stack.size()];
		for (int i =0; i < ans.length; i++)
			ans[i] = stack.get(i);
		for (Point ppp : p) {
			ppp.x += MIN.x;
			ppp.y += MIN.y;
		}
		return ans;
	}
		
	static void genSmallTests() { // 6 tests
		new Test(
				new Point[]{
						new Point(0, 0),
						new Point(1, 0),
						new Point(0, 1)
				},
				new Point[] {
						new Point(10, 0),
						new Point(10, 0),
						new Point(0, 10),
						new Point(0, 10),
						new Point(10, 10),
						new Point(10, 10),
						new Point(10, 10)
				}, 
				1
		).print();

		for (Point[] poly : new Point[][]{
			new Point[] {
					new Point(0, 0),
					new Point(1, 0),
					new Point(1, 1),
					new Point(0, 1)
			},
			new Point[] {
					new Point(0, 0),
					new Point(1, 1),
					new Point(0, 1)
			}
		} ) {
			int m = 2;
			Point[] q = new Point[poly.length * (2 * m + 1) * (2 * m + 1)];
			int p = 0;
			for (int x = -m; x <= m; x++) {
				for (int y = -m; y <= m; y++) {
					for (int i = 0; i < poly.length; i++) {
						q[p++] = new Point(x, y);
					}
				}
			}
			new Test(poly, q).print();
			Point dp = new Point(rnd.nextInt(MAXK / 3), rnd.nextInt(MAXK / 3));
			shift(poly, dp.x, dp.y);
			shift(q, dp.x, dp.y);
			new Test(poly, q).print();	
		}
			
		new Test(ellipsoid(MAXK, MAXK / 2, 100), 100).print();
	}
	
	static void gen100v10000() {
		for (int i = 1; i < 7; i++) {
			Point[] poly = subarray(ellipsoid(MAXK / (i + 5), MAXK / (20 - i), 100 * i), 0, 100);
			shift(poly, rnd.nextInt(MAXK / 2), rnd.nextInt(MAXK / 2));
			Point[] q = genRandomQueries(poly, 10000, -MAXK / 2, MAXK / 2, -MAXK / 2, MAXK / 2);
			new Test(poly, q).rotate().shuffleQueries().print();
		}
	}
	
	static void genBig() {
		Point[] poly = subarray(ellipsoid(MAXK / 2, MAXK, 20 * MAXN), 0, MAXN);
		int[] index = new int[poly.length];
		Point q = genRandomQueries(poly, 1, -MAXK, MAXK, -MAXK, MAXK)[0];
		for (int i = 0; i < index.length; i++)
			index[i] = i + 1;
		Point[] queries = new Point[poly.length];
		for (int i = 0; i < queries.length; i++) {
			queries[i] = q;
		}
		new Test(poly, queries, 1).print();
		for (int i = 0; i < poly.length; i++) {
			queries[i] = poly[i];
		}
		new Test(poly, queries).print();
		for (int i = 2; i <= 7; i++) {
			poly = subarray(ellipsoid(MAXK / i, MAXK / i, i * 5 * MAXN), 0, MAXN);
			shift(poly, rnd.nextInt(MAXK / 2), rnd.nextInt(MAXK / 2));
			new Test(poly, MAXM).rotate().print();
		}
	}
	
	public static void main(String[] args) {
		genSmallTests(); // 30%
		gen100v10000(); // 30%
		genBig(); // 40%
	}
}
