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

public class TestsGen {

	public static class Quary {
		boolean type;
		int index, key;

		Quary(boolean t) {
			type = t;
			index = key = 0;
		}

		Quary(boolean t, int i, int x) {
			type = t;
			index = i;
			key = x;
		}

		@Override
		public String toString() {
			if (type)
				return "! " + index + " " + key;
			else
				return "?";
		}

	}

	static int done = 0;

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

	static final int MAX_SIZE = (int) 1e5;
	static final int MAX_SIZE2 = 10000;
	static final int MAX_QUARYS = (int) 2e5;
	static final int MAX_QUARYS2 = 10000;
	static final int MAX_VALUE = (int) 1e9;

	static ArrayList<Integer> data = new ArrayList<Integer>();
	static ArrayList<Quary> quary = new ArrayList<Quary>();

	static void print() 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(data.size() + " " + quary.size());
		for (int i = 0; i < data.size() - 1; i++)
			out.print(data.get(i) + " ");
		out.println(data.get(data.size() - 1));
		for (int i = 0; i < quary.size(); i++)
			out.println(quary.get(i));
		data.clear();
		quary.clear();
		out.close();
	}

	static void genSimple() throws IOException {
		PrintWriter out;
		 out = new PrintWriter("../preliminary/01"); out.println("5 5");
		 out.println("2 4 6 8 10"); 
		 out.println("?"); 
		 out.println("! 2 7"); 
		 out.println("?"); 
		 out.println("! 3 8"); 
		 out.println("?"); 
		 out.close();
	}

	static void genSortingArray(int cnt, int val) {
		for (int i = 0; i < cnt; i++)
			data.add(rand.nextInt(val));
		Collections.sort(data);
	}

	static void genEqualArray(int cnt, int val) {
		int t = rand.nextInt(val);
		for (int i = 0; i < cnt; i++)
			data.add(t);
	}

	static void addRand(int cnt, int val) {
		for (int i = 0; i < cnt; i++)
			data.add(rand.nextInt(val));
	}

	static void changeElement(int pos, int val) {
		data.set(pos, val);
	}

	static void addChaos(int l, int r, int val) {
		for (int i = l; i < r; i++)
			changeElement(i, rand.nextInt(val));
	}

	static void genRandQuary(int val) throws IOException {
		genRandQuary(rand.nextBoolean(), val);
	}

	static void genRandQuary(boolean type, int val) throws IOException {
		quary.add(new Quary(type, rand.nextInt(data.size()) + 1, rand.nextInt(val)));
	}

	static void genRandQuary(boolean type, int val, int l, int r)
			throws IOException {
		quary.add(new Quary(type, rand.nextInt(r - l + 1) + l, rand
				.nextInt(val)));
	}

	static void genEqualQuary(int l, int r) {
		int t = (l > 0) ? data.get(l - 1) : 0;
		for (int i = l; i < r; i++) {
			quary.add(new Quary(true, i, t));
			if (rand.nextInt(5) == 0)
				quary.add(new Quary(false, i, t));
		}
	}

	static void allSorting(int val) {
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		for (int i = 0; i < data.size(); i++)
			tmp.add(rand.nextInt(val));
		Collections.sort(tmp);
		ArrayList<Quary> qq = new ArrayList<>();
		for (int i = 0; i < data.size(); i++)
			qq.add(new Quary(true, i, tmp.get(i)));
	}

	public static void main(String[] args) throws IOException {
		boolean f = (new File("../preliminary")).mkdir();
		f = new File("../tests").mkdir();

		genSimple();

		done = 0;

		// Small test n <= 10000 and m <= 10000
		// 1
		genSortingArray(100, 1000);
		print();

		// 2
		genEqualArray(10, 50);
		for (int i = 0; i < 20; i++)
			genRandQuary(rand.nextBoolean(), 100, 9, 10);
		print();

		// 3
		genEqualArray(10000, MAX_VALUE);
		int color = data.get(0);
		for (int i = 0; i < 10000 / 8; i++) {
			quary.add(new Quary(false));
			int l = rand.nextInt(10000 / 2) + 1;
			int r = rand.nextInt(10000 / 2) + 10000 / 2 + 1;
			int c1 = rand.nextInt(MAX_VALUE);
			int c2 = rand.nextInt(MAX_VALUE);
			quary.add(new Quary(true, l, c1));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, c2));
			quary.add(new Quary(false));
			quary.add(new Quary(true, l, color));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, color));
		}
		print();

		// 4
		genEqualArray(10000, MAX_VALUE);
		color = data.get(0);
		for (int i = 0; i < 10000 / 8; i++) {
			quary.add(new Quary(false));
			int l = rand.nextInt(10000 / 2) + 1;
			int r = rand.nextInt(10000 / 2) + 10000 / 2 + 1;
			int c1 = rand.nextInt(MAX_VALUE);
			int c2 = rand.nextInt(MAX_VALUE);
			quary.add(new Quary(true, l, c1));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, c2));
			quary.add(new Quary(false));
			quary.add(new Quary(true, l, color));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, color));
		}
		Collections.shuffle(quary, rand);
		print();

		// 5
		addRand(9999, 10000);
		allSorting(10000);
		Collections.shuffle(quary, rand);
		quary.add(new Quary(false));
		print();

		// 6
		addRand(7999, 10000);
		genEqualQuary(1, 8000);
		quary.add(new Quary(false));
		print();

		// 7
		genEqualArray(MAX_SIZE2, 300000);
		for (int i = 0; i < MAX_QUARYS2; i++)
			genRandQuary(rand.nextBoolean(), MAX_VALUE, MAX_SIZE2 / 2 - 2,
					MAX_SIZE2 / 2);
		print();

		// 8
		genSortingArray(MAX_SIZE2, 200000);
		for (int i = 0; i < MAX_QUARYS2; i++)
			genRandQuary(i % 2 == 0, MAX_VALUE, MAX_SIZE2 / 3 * 2 - 1,
					MAX_SIZE2 / 3 * 2);
		print();

		// 9
		genSortingArray(MAX_SIZE2, MAX_VALUE / 10);
		for (int i = 0; i < MAX_QUARYS2; i++)
			genRandQuary(i % 2 == 0, MAX_VALUE, MAX_SIZE2 / 3, MAX_SIZE2 / 3);
		print();

		// 10
		genSortingArray(MAX_SIZE2, MAX_VALUE);
		for (int i = 0; i < 19; i++) {
			for (int j = 0; j < MAX_QUARYS2 / 20; j++)
				genRandQuary(rand.nextBoolean(), MAX_VALUE, MAX_SIZE2 / 20
						* (i + 1) - 1, MAX_SIZE2 / 20 * (i + 1));
			genEqualQuary(MAX_SIZE2 / 20 * (i + 1) - 10, MAX_SIZE2 / 20 * (i + 1)
					+ 5);

		}
		print();

		// 11
		genSortingArray(MAX_SIZE2, MAX_VALUE);
		for (int i = 0; i < MAX_SIZE2; i++)
			genRandQuary(MAX_VALUE);
		print();
		
		// 12
		genEqualArray(10000, 1000000);
		color = data.get(0);
		for (int j = 0; j < 300; j++)
		{
			int l =  rand.nextInt(9000) + 1;
			int r = l + rand.nextInt(25);
			for (int i = l; i< r; i++)
				quary.add(new Quary(true, i, rand.nextInt(10000)));
			genEqualQuary(l, r);
		}
		print();

		// Big test
		// 13
		genEqualArray(MAX_SIZE, 300000);
		for (int i = 0; i < MAX_QUARYS; i++)
			genRandQuary(rand.nextBoolean(), MAX_VALUE, MAX_SIZE / 2 - 2,
					MAX_SIZE / 2);
		print();

		// 14
		genSortingArray(MAX_SIZE, 200000);
		for (int i = 0; i < MAX_QUARYS; i++)
			genRandQuary(i % 2 == 0, MAX_VALUE, MAX_SIZE / 3 * 2 - 1,
					MAX_SIZE / 3 * 2);
		print();

		// 15
		genSortingArray(MAX_SIZE, MAX_VALUE / 10);
		for (int i = 0; i < MAX_QUARYS; i++)
			genRandQuary(i % 2 == 0, MAX_VALUE, MAX_SIZE / 3, MAX_SIZE / 3);
		print();

		// 16
		genSortingArray(MAX_SIZE, MAX_VALUE);
		for (int i = 0; i < 19; i++) {
			for (int j = 0; j < MAX_QUARYS / 20; j++)
				genRandQuary(rand.nextBoolean(), MAX_VALUE, MAX_SIZE / 20
						* (i + 1) - 1, MAX_SIZE / 20 * (i + 1));
			genEqualQuary(MAX_SIZE / 20 * (i + 1) - 10, MAX_SIZE / 20 * (i + 1)
					+ 5);

		}
		print();

		// 17
		genSortingArray(MAX_SIZE, MAX_VALUE);
		for (int i = 0; i < MAX_SIZE; i++)
			genRandQuary(MAX_VALUE);
		print();

		// 18
		genSortingArray(MAX_SIZE - 1, MAX_VALUE);
		addRand(1, 123456);
		quary.add(new Quary(false));
		quary.add(new Quary(true, MAX_SIZE, MAX_VALUE));
		for (int i = 2; i < MAX_QUARYS; i++)
			quary.add(new Quary(false));
		print();

		// 19
		genEqualArray(MAX_SIZE, MAX_VALUE);
		color = data.get(0);
		for (int i = 0; i < MAX_QUARYS / 8; i++) {
			quary.add(new Quary(false));
			int l = rand.nextInt(MAX_SIZE / 2) + 1;
			int r = rand.nextInt(MAX_SIZE / 2) + MAX_SIZE / 2 + 1;
			int c1 = rand.nextInt(MAX_VALUE);
			int c2 = rand.nextInt(MAX_VALUE);
			quary.add(new Quary(true, l, c1));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, c2));
			quary.add(new Quary(false));
			quary.add(new Quary(true, l, color));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, color));
		}
		print();

		// 20
		genEqualArray(MAX_SIZE, MAX_VALUE);
		color = data.get(0);
		for (int i = 0; i < MAX_QUARYS / 41; i++) {
			quary.add(new Quary(false));
			int l = rand.nextInt(MAX_SIZE / 2) + 1;
			int r = rand.nextInt(MAX_SIZE / 2) + MAX_SIZE / 2 + 1;
			int c1 = rand.nextInt(MAX_VALUE);
			int c2 = rand.nextInt(MAX_VALUE);
			quary.add(new Quary(true, l, c1));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, c2));
			quary.add(new Quary(false));
			quary.add(new Quary(true, l, color));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, color));
		}
		Collections.shuffle(quary, rand);
		genEqualQuary(1, MAX_SIZE + 1);
		for (int i = 0; i < MAX_QUARYS / 41; i++) {
			quary.add(new Quary(false));
			int l = rand.nextInt(MAX_SIZE / 2) + 1;
			int r = rand.nextInt(MAX_SIZE / 2) + MAX_SIZE / 2 + 1;
			int c1 = rand.nextInt(MAX_VALUE);
			int c2 = rand.nextInt(MAX_VALUE);
			quary.add(new Quary(true, l, c1));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, c2));
			quary.add(new Quary(false));
			quary.add(new Quary(true, l, color));
			quary.add(new Quary(false));
			quary.add(new Quary(true, r, color));
		}
		print();

		return;
	}
}
