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

public class TestsGen {
	static int testcount = 0;

	static Random random = new Random(846734875);
	static int MAXC = (int) 1e9;
	static int MAXC2 = 100;
	static int MAXN = 100000;
	static int MAXK = 10;
	
	static void write(Block[] b, House[] h) {
		write(b, h, "tests", ++testcount);
	}

	static void write(Block[] b, House[] h, String folder, int testcount) {
		try {
			PrintWriter out = new PrintWriter(String.format("../%s/%02d", folder, testcount));
			System.out.println("Generating test #" + testcount);
			out.println(b.length + " " + h.length);
			for (Block bb : b) {
				out.println(bb.x1 + " " + bb.y1 + " " + bb.x2 + " " + bb.y2);
			}
			for (House hh : h) {
				out.println(hh.x + " " + hh.y);
			}
			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	static Block randBlock(int minx, int maxx, int miny, int maxy) {
		while (true) {
			int x1 = random.nextInt(maxx - minx + 1) + minx;
			int x2 = random.nextInt(maxx - minx + 1) + minx;
			int y1 = random.nextInt(maxy - miny + 1) + miny;
			int y2 = random.nextInt(maxy - miny + 1) + miny;
			if (x1 == x2 || y1 == y2)
				continue;
			Block b = new Block(x1, y1, x2, y2);
			if (b.inside(0, 0)) {
				continue;
			}
			return b;
		}
	}

	static Block randBlock() {
		return randBlock(-MAXC, MAXC, -MAXC, MAXC);
	}

	static House randHouse(Block[] b, int minx, int maxx, int miny, int maxy) {
		all: while (true) {
			int x = random.nextInt(maxx - minx + 1) + minx;
			int y = random.nextInt(maxy - miny + 1) + miny;
			for (Block bb : b) {
				if (bb.inside(x, y))
					continue all;
			}
			if (x != 0 || y != 0) {
				return new House(x, y);
			}
		}
	}

	static House randHouse(Block[] b, int MAXC) {
		return randHouse(b, -MAXC, MAXC, -MAXC, MAXC);
	}

	static House randHouse1(Block[] b, int MAXC) {
		int maxy = MAXC;
		for (Block bb : b) {
			if (bb.x1 < 0 && bb.x2 > 0 && bb.y1 >= 0) {
				maxy = Math.min(maxy, bb.y1);
			}
		}
		if (maxy == 0) return new House(0, 0);
		return new House(0, random.nextInt(maxy) + 1);
	}

	static House randHouse2(Block[] b, int MAXC) {
		House h = randHouse1(b, MAXC);
		int minx = -MAXC;
		int maxx = MAXC;
		for (Block bb : b) {
			if (bb.y1 < h.y && bb.y2 > h.y) {
				if (bb.x2 <= 0) {
					minx = Math.max(minx, bb.x2);
				}
				if (bb.x1 >= 0) {
					maxx = Math.min(maxx, bb.x1);
				}
			}
		}
		return new House(random.nextInt(maxx - minx + 1) + minx, h.y);
	}

	static House randHouse3(Block[] b, int MAXC) {
		House h = randHouse2(b, MAXC);
		int miny = -MAXC;
		int maxy = MAXC;
		for (Block bb : b) {
			if (bb.x1 < h.x && bb.x2 > h.x) {
				if (bb.y2 <= h.y) {
					miny = Math.max(miny, bb.y2);
				}
				if (bb.y1 >= h.y) {
					maxy = Math.min(maxy, bb.y1);
				}
			}
		}
		return new House(h.x, random.nextInt(maxy - miny + 1) + miny);
	}

	static void genRand(int n, int k, int MAXC) {
		Block[] b = new Block[n];
		for (int i = 0; i < n; i++) {
			b[i] = randBlock(-MAXC, MAXC, -MAXC, MAXC);
		}
		House[] h = new House[k];
		for (int i = 0; i < k; i++) {
			h[i] = randHouse(b, MAXC);
		}
		write(b, h);
	}

	static void genRand1(int n, int k, int MAXC) {
		Block[] b = new Block[n];
		House[] h = new House[k];
		all: while (true) {
			for (int i = 0; i < n; i++) {
				b[i] = randBlock(-MAXC, MAXC, -MAXC, MAXC);
			}
			for (int i = 0; i < k; i++) {
				h[i] = randHouse1(b, MAXC);
				if (h[i].y == 0) continue all;
			}
			break;
		}
		write(b, h);
	}

	static void genRand2(int n, int k, int MAXC) {
		Block[] b = new Block[n];
		for (int i = 0; i < n; i++) {
			b[i] = randBlock(-MAXC, MAXC, -MAXC, MAXC);
		}
		House[] h = new House[k];
		for (int i = 0; i < k; i++) {
			h[i] = randHouse2(b, MAXC);
		}
		write(b, h);
	}

	static Block goodBlock(House[] h, int ind, int MAXC) {
		int x = h[ind].x;
		int y = h[ind].y;
		int miny = Math.min(0, y);
		int maxy = Math.max(0, y);
		int x1, y1, x2, y2;
		while (true) {
			int yy = random.nextInt(maxy - miny + 1) + miny;
			y1 = yy;
			y2 = yy + 1;
			x1 = x - 1;
			x2 = x + 1;
			Block b = new Block(x1, y1, x2, y2);
			boolean good = true;
			for (int i = 0; i < ind; i++) {
				if (b.inside(h[i]))
					good = false;
			}
			if (good) {
				return b;
			}
		}
	}

	static Block goodBlock2(House[] h, int ind, int MAXC) {
		int x = h[ind].x;
		int y = h[ind].y;
		int minx = Math.min(0, x);
		int maxx = Math.max(0, x);
		int x1, y1, x2, y2;
		while (true) {
			int xx = random.nextInt(maxx - minx) + minx;
			x1 = xx;
			x2 = xx + 1;
			y1 = y - 1;
			y2 = y + 1;
			Block b = new Block(x1, y1, x2, y2);
			boolean good = true;
			for (int i = 0; i < ind; i++) {
				if (b.inside(h[i]))
					good = false;
			}
			if (good) {
				return b;
			}
		}
	}
	
	static Block goodBlock3(House[] h, int ind, int MAXC) {
		int x = h[ind].x;
		int y = h[ind].y;
		int minx = Math.min(0, x);
		int maxx = Math.max(0, x);
		int x1, y1, x2, y2;
		while (true) {
			int xx = random.nextInt(maxx - minx) + minx;
			x1 = xx;
			x2 = xx + 1;
			y1 = 0;
			y2 = y + 1;
			int t = random.nextInt(Math.abs(y) + 1);
			y2 = t * (int)Math.signum(y) + y + 1;
			if (y2 >= MAXC - 10) {
				if (y > 0) {
					y2 = (MAXC + y) / 2;
				}else {
					y2 = (-MAXC + y) / 2;
				}
			}
			Block b = new Block(x1, y1, x2, y2);
			boolean good = true;
			for (int i = 0; i < ind; i++) {
				if (b.inside(h[i]))
					good = false;
			}
			if (good) {
				return b;
			} else {
//				System.err.println("bad");
			}
		}
	}
	
	static void genRand3(int n, int k, boolean blockShort, int MAXC) {
		all: while (true) {
		ArrayList<Block> blocks = new ArrayList<>();
		for (int i = 0; i < n - 2 * k; i++) {
			blocks.add(randBlock(-MAXC, MAXC, -MAXC, MAXC));
		}
		House[] h = new House[k];
		for (int i = 0; i < k; i++) {
			while (true) {
				h[i] = randHouse3(blocks.toArray(new Block[blocks.size()]), MAXC);
				if (h[i].x == 0) {
					continue all;
				}
				blocks.add(goodBlock(h, i, MAXC));
				if (blockShort) {
					blocks.add(goodBlock3(h, i, MAXC));
				} else {
					blocks.add(goodBlock2(h, i, MAXC));
				}
				Solution sol = new Solution(blocks.toArray(new Block[blocks
						.size()]));
				if (h[i].x != 0) {
//					System.err.println("1" + sol.solveLen(h[i]));
//					System.err.println("2" + sol.canZeroTurn(h[i]));
				}
				if (sol.solveLen(h[i]) == 3 && !sol.canZeroTurn(h[i])) {
					break;
				}
				blocks.remove(blocks.size() - 1);
				blocks.remove(blocks.size() - 1);
			}
		}
		write(blocks.toArray(new Block[blocks.size()]), h);
		break;
		}
	}
	
	static void genNeg(int n, int k, int MAXC) {
		Block[] b = new Block[n];
		for (int i = 0; i < n; i++) {
			b[i] = randBlock(-MAXC, MAXC, -MAXC, MAXC);
		}
		House[] h = new House[k];
		for (int i = 0; i < k; i++) {
			h[i] = randHouse(b, -MAXC, MAXC, -MAXC, -1);
		}
		write(b, h);
	}
	
	static void genSample1() {
		Block[] b = new Block[1];
		b[0] = new Block(-2, 1, 9, 2);
		House[] h = new House[2];
		h[0] = new House(2, 0);
		h[1] = new House(3, 3);
		write(b, h, "preliminary", 1);
	}

	static void genSample2() {
		Block[] b = new Block[2];
		b[0] = new Block(0, 2, 2, 4);
		b[1] = new Block(1, 0, 4, 2);
		House[] h = new House[1];
		h[0] = new House(3, 3);
		write(b, h, "preliminary", 2);
	}
	
	static void genSample3() {
		Block[] b = new Block[0];
		House[] h = new House[2];
		h[0] = new House(0, -1);
		h[1] = new House(0, 1);
		write(b, h, "preliminary", 3);
	}
	
	static void genHand1(int v) {
		Block[] b = new Block[0];
		House[] h = new House[8];
		h[0] = new House(-v, -v);
		h[1] = new House(-v, 0);
		h[2] = new House(-v, v);
		h[3] = new House(v, -v);
		h[4] = new House(v, 0);
		h[5] = new House(v, v);
		h[6] = new House(0, v);
		h[7] = new House(0, -v);
		write(b, h);
	}
	
	public static void main(String[] args) throws IOException {
		genSample1();
		genSample2();
		genSample3();
		
		genHand1(1);
		genRand(0, 3, MAXC2);
		genRand1(0, 5, MAXC2);
		genRand2(0, 8, MAXC2);
		genNeg(0, 10, MAXC2);
		
		genRand(10, 10, 50);
		genRand1(3, 10, MAXC2);
		genRand2(8, 10, MAXC2);
		genRand3(23, 10, false, 50);
		genRand3(25, 10, true, MAXC2);

		genRand(50, 10, MAXC2);
		genRand1(50, 10, MAXC2);
		genRand2(50, 10, MAXC2);
		genRand3(50, 10, false, MAXC2);
		genRand3(50, 10, true, MAXC2);
		
		genHand1(MAXC);
		genRand(0, 10, MAXC);
		genRand1(0, 4, MAXC);
		genRand2(0, 7, MAXC);
		genNeg(0, 5, MAXC);
		
		genRand(50, 10, 100000);
		genRand1(49, 10, 100000);
		genRand2(16, 10, 1000000);
		genRand3(35, 10, false, 1000000);
		genRand3(42, 10, true, 10000);

		genRand(50, 10, MAXC);
		genRand1(50, 10, MAXC);
		genRand2(50, 10, MAXC);
		genRand3(50, 10, false, MAXC);
		genRand3(50, 10, true, MAXC);

		genRand3(5304, 5, false, 100000);
		genRand3(934, 7, true, 100000);
		genRand3(9999, 10, false, 100000);
		genRand3(3594, 1, false, 100000);
		genRand3(2498, 2, true, 100000);
		
		for (int iter = 0; iter < 2; iter++) {
			genRand(random.nextInt(MAXN), 10, MAXC);
			genRand1(random.nextInt(MAXN), 10, MAXC);
			genRand2(random.nextInt(MAXN), 10, MAXC);
			genRand3(random.nextInt(MAXN), 10, false, MAXC);
			genRand3(random.nextInt(MAXN), 10, true, MAXC);
		}
		
		genRand(MAXN, 10, MAXC);
		genRand1(MAXN, 10, MAXC);
		genRand2(MAXN, 10, MAXC);
		genRand3(MAXN, 10, false, MAXC);
		genRand3(MAXN, 10, true, MAXC);
		
//		genRand(10, 1);
//		genRand(10, 10);
//		genRand(100, 10);
//		genRand(1000, 10);
//		genRand(10000, 10);
//		genRand(100000, 10);
//		genRand1(10, 10);
//		genRand1(100, 10);
//		genRand1(1000, 10);
//		genRand1(10000, 10);
//		genRand1(100000, 10);
//		genRand2(10, 10);
//		genRand2(100, 10);
//		genRand2(1000, 10);
//		genRand2(10000, 10);
//		genRand2(100000, 10);
//		genRand3(10, 10, false);
//		genRand3(100, 10, false);
//		genRand3(1000, 10, false);
//		genRand3(10000, 10, false);
//		genRand3(100000, 10, false);
//		genRand3(10, 10, true);
//		genRand3(100, 10, true);
//		genRand3(1000, 10, true);
//		genRand3(10000, 10, true);
//		genRand3(100000, 10, true);
	}

}

class House {
	int x, y;

	House(int xx, int yy) {
		x = xx;
		y = yy;
	}
}

class Block {
	int x1, y1, x2, y2;

	Block(int xx1, int yy1, int xx2, int yy2) {
		x1 = Math.min(xx1, xx2);
		x2 = Math.max(xx1, xx2);
		y1 = Math.min(yy1, yy2);
		y2 = Math.max(yy1, yy2);
	}

	boolean inside(int x, int y) {
		return x > x1 && x < x2 && y > y1 && y < y2;
	}

	boolean inside(House h) {
		return inside(h.x, h.y);
	}
}

class Solution {
	boolean inside(long x1, long x2, long y) {
		return (y > x1 && y < x2) || (y > x2 && y < x1);
	}

	Block[] blocks;

	boolean isFreeX(long x, long fromY, long toY) {
		for (Block b : blocks) {
			if (inside(b.x1, b.x2, x)
					&& (inside(fromY, toY, b.y1) || inside(fromY, toY, b.y2) || inside(
							b.y1, b.y2, fromY))) {
				return false;
			}
		}
		return true;
	}

	boolean isFreeY(long y, long fromX, long toX) {
		for (Block b : blocks) {
			if (inside(b.y1, b.y2, y)
					&& (inside(fromX, toX, b.x1) || inside(fromX, toX, b.x2) || inside(
							b.x1, b.x2, fromX))) {
				return false;
			}
		}
		return true;
	}

	long findUp(long x, long y) {
		long ret = Long.MAX_VALUE;
		for (Block b : blocks) {
			if (inside(b.x1, b.x2, x) && b.y1 >= y) {
				ret = Math.min(ret, b.y1);
			}
		}
		return ret;
	}

	long findDown(long x, long y) {
		long ret = Long.MIN_VALUE;
		for (Block b : blocks) {
			if (inside(b.x1, b.x2, x) && b.y2 <= y) {
				ret = Math.max(ret, b.y2);
			}
		}
		return ret;
	}

	class Event implements Comparable<Event> {
		int type;
		long y;

		@Override
		public int compareTo(Event o) {
			if (y < o.y)
				return -1;
			if (y > o.y)
				return 1;
			return type - o.type;
		}

		Event(long a, int b) {
			y = a;
			type = b;
		}
	}

	long findSegment(long x1, long x2, long y1, long y2) {
		if (y1 == y2) {
			if (isFreeY(y1, x1, x2)) {
				return y1;
			} else {
				return -1;
			}
		}
		ArrayList<Event> al = new ArrayList<>();
		for (Block b : blocks) {
			if (inside(x1, x2, b.x1) || inside(x1, x2, b.x2)
					|| inside(b.x1, b.x2, x1)) {
				al.add(new Event(b.y1, 1));
				al.add(new Event(b.y2, -1));
			}
		}
		al.add(new Event(y1, 0));
		al.add(new Event(y2, 0));
		Collections.sort(al);
		int h = 0;
		for (Event e : al) {
			h += e.type;
			if (h == 0 && e.y >= y1 && e.y <= y2) {
				return e.y;
			}
		}
		return -1;
	}

	Solution(Block[] b) {
		this.blocks = b;
	}

	int solveLen(House h) {
		long x = h.x;
		long y = h.y;

		if (x == 0) {
			if (y > 0) {
				if (isFreeX(0, 0, y)) {
					return 1;
				}
			}
			return -1;
		}
		{
			if (y >= 0 && isFreeX(0, 0, y)
					&& isFreeY(y, Math.min(0, x), Math.max(0, x))) {
				return 2;
			}
		}

		if (y >= 0) {
			long y1 = findUp(0, 0);
			long y2 = findDown(x, y);
			y1 = Math.min(y1, y);
			y2 = Math.max(y2, 0);
			if (y2 <= y1) {
				long yy = findSegment(Math.min(x, 0), Math.max(x, 0), y2, y1);
				if (yy != -1) {
					return 3;
				}
			}
		}
		{
			long y1 = findUp(0, 0);
			long y2 = findUp(x, y);
			if (y1 >= y && y2 >= 0) {
				long yy = findSegment(Math.min(x, 0), Math.max(x, 0),
						Math.max(0, y), Math.min(y1, y2));
				if (yy != -1) {
					return 3;
				}
			}
		}
		return -1;
	}

	boolean canZeroTurn(House h) {
//		if (h.x < 0) {
//			System.err.println(isFreeY(0, Math.min(0, h.x), Math.max(0, h.x)));
//			System.err.println(isFreeX(h.x, Math.min(0, h.y), Math.max(0, h.y)));
//			h.x += 0;
//		}
		return isFreeY(0, Math.min(0, h.x), Math.max(0, h.x))
				&& isFreeX(h.x, Math.min(0, h.y), Math.max(0, h.y));
	}
}