import java.io.*; import java.util.*; import java.util.concurrent.ThreadLocalRandom; import java.util.function.IntUnaryOperator; import java.util.function.LongUnaryOperator; import java.util.stream.Collectors; public class Main { static boolean isLocal; Random rand = new Random(); In in = new In(System.in); PrintStream out = System.out; long inf = 0x1fffffffffffffffL; int iinf = 0x3fffffff; long startTime; public static final long[] TABLE = new long[364]; public static final int[] COST = {0,10000000,7071067,5773502,5000000,4472135,4082482,3779644,3535533,3333333,3162277,3015113,2886751,2773500,2672612,2581988,2500000,2425356,2357022,2294157,2236067,2182178,2132007,2085144,2041241,2000000,1961161,1924500,1889822,1856953,1825741,1796053,1767766,1740776,1714985,1690308,1666666,1643989,1622214,1601281,1581138,1561737,1543033,1524985,1507556,1490711,1474419,1458649,1443375,1428571,1414213,1400280,1386750,1373605,1360827,1348399,1336306,1324532,1313064,1301889,1290994,1280368,1270001,1259881,1250000,1240347,1230914,1221694,1212678,1203858,1195228,1186781,1178511,1170411,1162476,1154700,1147078,1139605,1132277,1125087,1118033,1111111,1104315,1097642,1091089,1084652,1078327,1072112,1066003,1059997,1054092,1048284,1042572,1036951,1031421,1025978,1020620,1015346,1010152,1005037,1000000,995037,990147,985329,980580,975900,971285,966736,962250,957826,953462,949157,944911,940720,936585,932504,928476,924500,920574,916698,912870,909090,905357,901669,898026,894427,890870,887356,883883,880450,877058,873704,870388,867109,863868,860662,857492,854357,851256,848188,845154,842151,839181,836242,833333,830454,827605,824786,821994,819231,816496,813788,811107,808452,805822,803219,800640,798086,795557,793051,790569,788110,785674,783260,780868,778498,776150,773823,771516,769230,766964,764719,762492,760285,758098,755928,753778,751646,749531,747435,745355,743294,741249,739221,737209,735214,733235,731272,729324,727392,725476,723574,721687,719815,717958,716114,714285,712470,710669,708881,707106,705345,703597,701862,700140,698430,696733,695048,693375,691714,690065,688428,686802,685188,683585,681994,680413,678844,677285,675737,674199,672672,671156,669649,668153,666666,665190,663723,662266,660818,659380,657951,656532,655121,653720,652328,650944,649569,648203,646846,645497,644156,642824,641500,640184,638876,637576,636284,635000,633724,632455,631194,629940,628694,627455,626224,625000,623782,622572,621369,620173,618984,617802,616626,615457,614295,613139,611990,610847,609710,608580,607456,606339,605227,604122,603022,601929,600841,599760,598684,597614,596549,595491,594438,593390,592348,591312,590281,589255,588235,587220,586210,585205,584206,583211,582222,581238,580258,579284,578314,577350,576390,575435,574484,573539,572598,571661,570730,569802,568880,567961,567047,566138,565233,564332,563436,562543,561655,560772,559892,559016,558145,557278,556414,555555,554700,553848,553001,552157,551317,550481,549649,548821,547996,547175,546358,545544,544734,543928,543125,542326,541530,540738,539949,539163,538381,537603,536828,536056,535287,534522,533760,533001,532246,531494,530744,529998,529256,528516,527779,527046,526315,525588,524863,524142,523423,522708,521995,521286,520579,519875,519174,518475,517780,517087,516397,515710,515026,514344,513665,512989,512315,511644,510976,510310,509647,508986,508328,507673,507020,506369,505721,505076,504433,503792,503154,502518,501885,501254,500626,500000}; public static final int S = 14; public static final int SS = 196; public static final int N = 3000; public static final int T = 400; int curTurn; int corCollabo = 1; int corMoney = 1000000; long solve(int seed) { startTime = System.currentTimeMillis(); Arrays.setAll(TABLE, i -> rand.next()); in(); // 80 10 424367600 // 80 20 450836500 // 80 30 439329940 // 80 50 416846380 // 50 50 404948590 // 70 50 416677250 // 90 50 417352330 // 100 50 402903920 // 150 50 344831110 int u1 = 80; State2 state = new State2(); int nj = 0; int lastU = 0; Action next = null; while (curTurn < T) { if (next == null) { for (Action ac : state.actions()) { ac.open(); if (next == null || next.score < ac.score) { next = ac; } } } boolean c1 = corMoney >= COST[corCollabo]; int cd = COST[corCollabo] - COST[corCollabo + 1]; int ud = !c1 ? 0 : (next.opened.score - lastU) * 60; int e1 = !c1 ? -1 : (T - curTurn) * ud - cd - 50000 - COST[corCollabo]; int e2 = Math.max(1, u1 - nj) * cd - ud - 50000; int e3 = 50000 - cd - ud; // debug(e1, e2, e3); if (e2 > e1 && e2 > e3) { corCollabo++; corMoney += 60 * lastU; ask2(); } else if (e1 > e3) { lastU = next.opened.score; corMoney += 60 * lastU - COST[corCollabo]; nj++; ask1(next.x, next.v); state = next.opened; next = null; } else { corMoney += 50000 + 60 * lastU; ask3(); } } // int u2 = 50; // State2 state = new State2(); // // State2 result = beamSearch(new State2(), trace, 10, 100000); // // debug(result.score); // if (!isLocal) { // corMoney = in.nextInt(); // in.nextInt(); // } // // int money = 1000000; // int lastU = 0; // int nj = 0; // for (int i = 1; i < u2; i++) { // corCollabo++; // ask2(); // } // while (true) { // while (corMoney < COST[corCollabo]) { // corMoney += 50000 + 60 * lastU; // ask3(); // } // // Action best = null; // for (Action next : state.actions()) { // next.open(); // if (best == null || best.score < next.score) { // best = next; // } // } // state = best.opened; // // // debug(k++, pos(action.x), action.v, action.opened.score); // if ((best.opened.score - lastU) * 60 * (T - curTurn) < 900000) { // debug(nj); // break; // } //// debug((best.opened.score - lastU) * (T - curTurn)); // lastU = best.opened.score; // corMoney += 60 * lastU - COST[corCollabo]; // nj++; // ask1(best.x, best.v); // if (curTurn >= T) { // break; // } // } // while (curTurn < T) { // corMoney += 60 * lastU; // ask3(); // } // // int u1 = 80; // int[] u2 = {30, 20}; // // Trace trace = new Trace(); // State2 result = greedy(new State2(), trace, u1); //// State2 result = beamSearch(new State2(), trace, 10, 100000); //// debug(result.score); // if (!isLocal) { // corMoney = in.nextInt(); // in.nextInt(); // } //// int money = 1000000; // int lastU = 0; // int nj = 0; // List actions = trace.trace(result.id); // for (Action action : actions) { // for (int i = 0; nj < u2.length && i < u2[nj]; i++) { // corCollabo++; // ask2(); // } // while (corMoney < COST[corCollabo]) { // corMoney += 50000 + 60 * lastU; // ask3(); // } //// debug(k++, pos(action.x), action.v, action.opened.score); // if ((action.opened.score - lastU) * (T - curTurn) < 30000) { // break; // } // debug((action.opened.score - lastU) * (T - curTurn)); // lastU = action.opened.score; // corMoney += 60 * lastU - COST[corCollabo]; // nj++; // ask1(action.x, action.v); // if (curTurn >= T) { // break; // } // } // while (curTurn < T) { // corMoney += 60 * lastU; // ask3(); // } return isLocal ? corMoney : 0; } int px(int x, boolean v) { return v ? x : x % S * S + x / S; } int py(int x, boolean v) { return v ? x + S : x % S * S + x / S + 1; } void ask1(int x, boolean v) { Pos px = pos(px(x, v)); Pos py = pos(py(x, v)); out.println("1 " + (px.x+1) + " " + (px.y+1) + " " + (py.x+1) + " " + (py.y+1)); out.flush(); curTurn++; if (!isLocal && curTurn < T) { corMoney = in.nextInt(); in.nextInt(); } } void ask2() { out.println(2); out.flush(); curTurn++; if (!isLocal && curTurn < T) { corMoney = in.nextInt(); in.nextInt(); } } void ask3() { out.println(3); out.flush(); curTurn++; if (!isLocal && curTurn < T) { corMoney = in.nextInt(); in.nextInt(); } } Pos[] fs, ts; void in() { Pos.init(S); in.nextInt(); in.nextInt(); fs = new Pos[N]; ts = new Pos[N]; for (int i = 0; i < N; i++) { int a = in.nextInt() - 1; int b = in.nextInt() - 1; int c = in.nextInt() - 1; int d = in.nextInt() - 1; fs[i] = pos(a, b); ts[i] = pos(c, d); } } Pos pos(int x, int y) { return Pos.instances[y * S + x]; } Pos pos(int z) { return Pos.instances[z]; } static class Pos implements Comparable { static Pos[] instances = new Pos[SS]; static Pos[] moved = new Pos[4 * SS]; static void init(int n) { for (int i = 0; i < n * n; i++) { instances[i] = new Pos(i % n, i / n, i); } for (int i = 0; i < n * n; i++) { for (int d = 0; d < 4; d++) { // LURD int nx = i % n + (d - 1) % 2; int ny = i / n + (d - 2) % 2; if (0 <= nx && nx < n && 0 <= ny && ny < n) { moved[i * 4 + d] = instances[ny * n + nx]; } } } } final int x, y, z; private Pos(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } Pos moved(int d) { return moved[z * 4 + d]; } int dist(Pos o) { return Math.abs(x - o.x) + Math.abs(y - o.y); } Pos[] neighbors() { Pos[] p = new Pos[4]; int i = 0; if ((p[i] = moved(0)) != null) i++; if ((p[i] = moved(1)) != null) i++; if ((p[i] = moved(2)) != null) i++; if ((p[i] = moved(3)) != null) i++; return i == 4 ? p : Arrays.copyOf(p, i); } @Override public int compareTo(Pos o) { return Integer.compare(z, o.z); } @Override public boolean equals(Object o) { return o instanceof Pos && z == ((Pos)o).z; } @Override public int hashCode() { return z; } @Override public String toString() { return String.format("(%d, %d)", x, y); } } // class State { // int collabo; // int money; // BitSet vert; // BitSet hori; // // int constructCost() { // return COST[collabo]; // } // } State2 initialState() { return new State2(); } class State2 implements Comparable { int id; State2 prev; int score; long hash; BitSet vert; // | BitSet hori; // - int[] dist; int[] uses; State2() { this.id = -1; this.hash = 0; this.vert = new BitSet(SS); this.hori = new BitSet(SS); this.dist = new int[N]; this.uses = new int[N]; for (int i = 0; i < N; i++) { dist[i] = Math.abs(fs[i].x - ts[i].x) + Math.abs(fs[i].y - ts[i].y); } } State2(State2 prev) { this.id = prev.id; this.prev = prev; this.score = prev.score; this.hash = prev.hash; this.vert = (BitSet)prev.vert.clone(); this.hori = (BitSet)prev.hori.clone(); this.dist = prev.dist.clone(); this.uses = prev.uses.clone(); } boolean highway(Pos p, int d) { if ((d & 1) == 0) { // LURD return hori.get(p.z - (d>>1^1)); } else { return vert.get(p.z - (d>>1^1) * S); } } int dist(int d, int u) { return d * 1000 - u * 777; } void update(int x, boolean v) { int px = px(x, v); int py = py(x, v); (v ? vert : hori).set(px); hash ^= TABLE[x + (v ? 182 : 0)]; Deque deque1 = new ArrayDeque<>(); Deque deque2 = new ArrayDeque<>(); BitSet fromY = new BitSet(SS); deque1.add(pos(px)); deque1.add(pos(py)); deque2.add(pos(px)); deque2.add(pos(py)); fromY.set(py); int[] ds = new int[SS]; int[] us = new int[SS]; Arrays.fill(ds, 30); ds[px] = 0; ds[py] = 0; while (!deque1.isEmpty() || !deque2.isEmpty()) { Pos p1 = deque1.isEmpty() ? null : deque1.peekFirst(); Pos p2 = deque2.isEmpty() ? null : deque2.peekFirst(); Pos p; boolean h = p2 == null || p1 != null && dist(ds[p1.z], us[p1.z]) < dist(ds[p2.z], us[p2.z]); if (h) { p = deque1.removeFirst(); } else { p = deque2.removeFirst(); } for (int i = 0; i < 4; i++) { Pos q = p.moved(i); if (q == null || highway(p, i) != h) { continue; } int nd = ds[p.z] + 1; int nu = us[p.z] + (h ? 1 : 0); if (dist(ds[q.z], us[q.z]) > dist(nd, nu)) { ds[q.z] = nd; us[q.z] = nu; fromY.set(q.z, fromY.get(p.z)); deque1.addLast(q); deque2.addLast(q); } } } for (int i = 0; i < N; i++) { if (fromY.get(fs[i].z) == fromY.get(ts[i].z)) { continue; } int nd = ds[fs[i].z] + ds[ts[i].z] + 1; int nu = us[fs[i].z] + us[ts[i].z] + 1; if (dist(dist[i], uses[i]) > dist(nd, nu)) { score += nu - uses[i]; dist[i] = nd; uses[i] = nu; } } } static int[] ord = new int[182]; static { Arrays.setAll(ord, i -> i); } List actions() { List nexts = new ArrayList<>(); for (int ii = 0; ii < 60; ii++) { int j = ii + rand.next(182 - ii); int i = ord[j]; ord[j] = ord[ii]; ord[ii] = i; if (!vert.get(i)) { nexts.add(new Action(this, hash ^ TABLE[i + 182], i, true)); } if (!hori.get(i)) { nexts.add(new Action(this, hash ^ TABLE[i], i, false)); } } return nexts; } void advance(Trace trace, Action action) { hash = action.hash; score = action.score; id = trace.add(action, id); } State2 copy() { return new State2(this); } @Override public int compareTo(State2 o) { return Integer.compare(score, o.score); } } class Action implements Comparable { State2 prev; State2 opened; long hash; int score; int x; boolean v; Action(State2 prev, long hash, int x, boolean v) { this.prev = prev; this.hash = hash; this.x = x; this.v = v; } void open() { opened = prev.copy(); opened.update(x, v); score = opened.score; } @Override public int compareTo(Action o) { return Integer.compare(o.score, score); } } static class Trace { List log = new ArrayList<>(); List prev = new ArrayList<>(); int add(Action action, int pi) { log.add(action); prev.add(pi); return log.size() - 1; } List trace(int id) { List actions = new ArrayList<>(); while (id != -1) { actions.add(log.get(id)); id = prev.get(id); } Collections.reverse(actions); return actions; } Action first(int id) { Action first = null; while (id != -1) { first = log.get(id); id = prev.get(id); } return first; } void clear() { log.clear(); prev.clear(); } } State2 beamSearch(State2 initialState, Trace trace, int beamWidth, long timeLimit, int maxTurn) { long[] hashes = new long[1 << 20]; initialState.id = -1; State2[] beam = {initialState}; State2 best = null; for (int turn = 1; ; turn++) { boolean sorted = false; int numCand = 0; Action[] cand = new Action[beamWidth * 2]; for (State2 state : beam) { if (state == null) { break; } for (Action action : state.actions()) { int key = (int)(action.hash & 0xfffff); if (hashes[key] != action.hash) { hashes[key] = action.hash; action.open(); if (sorted && cand[beamWidth - 1].score > action.score) { continue; } cand[numCand++] = action; if (numCand == cand.length) { Arrays.sort(cand, Comparator.reverseOrder()); numCand = beamWidth; sorted = true; } } } } Arrays.sort(cand); int size = Math.min(beamWidth, numCand); State2[] next = new State2[size]; int j = 0; State2 found = null; for (int i = 0; i < numCand && j < size; i++) { Action action = cand[i]; State2 copy = action.opened; copy.advance(trace, action); if (best == null || best.score < copy.score) { best = copy; } if (turn == maxTurn) { if (found == null || found.score < copy.score) { found = copy; } continue; } next[j++] = copy; } if (found != null) { return found; } if (j == 0 || elapsed(timeLimit)) { throw new RuntimeException(); } beam = next; } } State2 greedy(State2 state, Trace trace, int maxTurn) { state.id = -1; for (int turn = 1; ; turn++) { Action best = null; for (Action next : state.actions()) { next.open(); if (best == null || best.score < next.score) { best = next; } } state = best.opened; state.advance(trace, best); if (turn == maxTurn) { return state; } } } static void debug(Object... args) { if (!isLocal) { return; } if (args == null || args.getClass() != Object[].class) { args = new Object[] {args}; } System.err.println(Arrays.stream(args).map(obj -> { Class clazz = obj == null ? null : obj.getClass(); return clazz == byte[].class ? Arrays.toString((byte[])obj) : clazz == short[].class ? Arrays.toString((short[])obj) : clazz == int[].class ? Arrays.toString((int[])obj) : clazz == long[].class ? Arrays.toString((long[])obj) : clazz == char[].class ? Arrays.toString((char[])obj) : clazz == float[].class ? Arrays.toString((float[])obj) : clazz == double[].class ? Arrays.toString((double[])obj) : clazz == boolean[].class ? Arrays.toString((boolean[])obj) : obj instanceof Object[] ? Arrays.deepToString((Object[])obj) : String.valueOf(obj); }).collect(Collectors.joining(" "))); } long elapsed() { return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1)); } boolean elapsed(long timeLimit) { return elapsed() >= timeLimit; } public static void main(String[] args) { new Main().solve(0); } static class BinarySearchTree> implements Iterable { private final int n; private final Object[] a; private int size; public BinarySearchTree(int n) { this.n = n; this.a = new Object[n]; } public int size() { return size; } public void add(E element) { if (size < n) { int i = size++; while (i > 0) { int parent = (i - 1) / 2; if (get(parent).compareTo(element) <= 0) { break; } a[i] = a[parent]; i = parent; } a[i] = element; } else if (n > 0 && get(0).compareTo(element) < 0) { int i = 0; while (i * 2 + 1 < n) { int child = i * 2 + 1; if (child + 1 < n && get(child).compareTo(get(child + 1)) > 0) { child++; } if (get(child).compareTo(element) >= 0) { break; } a[i] = a[child]; i = child; } a[i] = element; } } @SuppressWarnings("unchecked") private E get(int index) { return (E)a[index]; } @Override public Iterator iterator() { return new Iterator() { private int i = 0; @Override public boolean hasNext() { return i < size; } @Override public E next() { return get(i++); } }; } } static class Random { private long x, y, z, w; Random() { this(ThreadLocalRandom.current().nextLong()); } Random(long seed) { this.x = seed; for (int i = 0; i < 20; i++) { rand(); } } private long rand() { long t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >>> 19) ^ t ^ (t >>> 8); return x & 0x7fffffff; } long next() { return rand() << 31 | rand(); } int next(int n) { return (int)(rand() % n); } int next(int l, int r) { return (int)(rand() % (r - l) + l); } double nextDouble() { return rand() / 2147483647.0; } } static class In { private final BufferedReader reader; private StringTokenizer tokenizer; In(InputStream input) { this.reader = new BufferedReader(new InputStreamReader(input), 0x10000); } String next() { try { while (tokenizer == null || !tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } } catch (IOException ignored) { } return tokenizer.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } char[] nextCharArray() { return next().toCharArray(); } String[] nextStringArray(int n) { String[] s = new String[n]; for (int i = 0; i < n; i++) { s[i] = next(); } return s; } char[][] nextCharGrid(int n, int m) { char[][] a = new char[n][m]; for (int i = 0; i < n; i++) { a[i] = next().toCharArray(); } return a; } int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } int[] nextIntArray(int n, IntUnaryOperator op) { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsInt(nextInt()); } return a; } int[][] nextIntMatrix(int h, int w) { int[][] a = new int[h][w]; for (int i = 0; i < h; i++) { a[i] = nextIntArray(w); } return a; } long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = nextLong(); } return a; } long[] nextLongArray(int n, LongUnaryOperator op) { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = op.applyAsLong(nextLong()); } return a; } long[][] nextLongMatrix(int h, int w) { long[][] a = new long[h][w]; for (int i = 0; i < h; i++) { a[i] = nextLongArray(w); } return a; } List> nextEdges(int n, int m, boolean directed) { List> res = new ArrayList<>(); for (int i = 0; i < n; i++) { res.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int u = nextInt() - 1; int v = nextInt() - 1; res.get(u).add(v); if (!directed) { res.get(v).add(u); } } return res; } } }