import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; public class Main { static long startTime; static long limitTime = 1800; static long limitTime1; static int N, T; static int W = 14; static int W1 = 13; static int W2 = 196; static int W21 = 182; static Obj[] arr; static int[] dx = {1, 0, -1, 0}; static int[] dy = {0, 1, 0, -1}; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); init(br); solve(br); } static void init(BufferedReader br) throws Exception { startTime = System.currentTimeMillis(); String[] sa = br.readLine().split(" "); N = Integer.parseInt(sa[0]); T = Integer.parseInt(sa[1]); limitTime1 = limitTime / T; arr = new Obj[N]; for (int i = 0; i < N; i++) { sa = br.readLine().split(" "); Obj o = new Obj(); o.a = Integer.parseInt(sa[0]) - 1; o.b = Integer.parseInt(sa[1]) - 1; o.c = Integer.parseInt(sa[2]) - 1; o.d = Integer.parseInt(sa[3]) - 1; o.ab = toInt(o.a, o.b); o.cd = toInt(o.c, o.d); arr[i] = o; } } static int solve(BufferedReader br) throws Exception { int numGoal = 20; int cost = (int) (10000000 / Math.sqrt(numGoal)); boolean[][] x = new boolean[W1][W]; boolean[][] y = new boolean[W][W1]; int preMax = 0; for (int t = 0; t < T; t++) { String[] sa = br.readLine().split(" "); int money = Integer.parseInt(sa[0]); int num = Integer.parseInt(sa[1]); if (num < numGoal) { System.out.println(2); continue; } if (money < cost) { System.out.println(3); continue; } long limit = startTime + limitTime1 * (t + 1); int max = 0; int maxdir = 0; int maxx = 0; int maxy = 0; Set set = new HashSet<>(); while (System.currentTimeMillis() < limit) { int r = (int) (Math.random() * W21); if (!set.add(r)) { continue; } { int i = r / W; int j = r % W; if (x[i][j]) { continue; } x[i][j] = true; int[] cnts = getCnts(x, y); int sum = 0; for (int k = 0; k < N; k++) { sum += cnts[k]; } if (sum > max) { max = sum; maxdir = 1; maxx = i; maxy = j; } x[i][j] = false; } { int i = r / W1; int j = r % W1; if (y[i][j]) { continue; } y[i][j] = true; int[] cnts = getCnts(x, y); int sum = 0; for (int k = 0; k < N; k++) { sum += cnts[k]; } if (sum > max) { max = sum; maxdir = 2; maxx = i; maxy = j; } y[i][j] = false; } } int val = (max - preMax) * 60 * (T - t); if (val - cost < 50000) { System.out.println(3); continue; } StringBuilder sb = new StringBuilder(); sb.append(1); sb.append(' ').append(maxx + 1); sb.append(' ').append(maxy + 1); if (maxdir == 1) { x[maxx][maxy] = true; sb.append(' ').append(maxx + 2); sb.append(' ').append(maxy + 1); } else { y[maxx][maxy] = true; sb.append(' ').append(maxx + 1); sb.append(' ').append(maxy + 2); } System.out.println(sb.toString()); preMax = max; } int score = 0; return score; } static int[] dist = new int[W2]; static int[] getCnts(boolean[][] x, boolean[][] y) { int[] ret = new int[N]; for (int i = 0; i < N; i++) { Obj o = arr[i]; Arrays.fill(dist, Integer.MAX_VALUE); dist[o.ab] = 0; PriorityQueue que = new PriorityQueue(); Node first = new Node(o.ab, 0); que.add(first); while (!que.isEmpty()) { Node cur = que.poll(); if (cur.v == o.cd) { break; } if (cur.d > dist[cur.v]) { continue; } int cx = cur.v / W; int cy = cur.v % W; for (int k = 0; k < 4; k++) { int nx = cx + dx[k]; int ny = cy + dy[k]; if (nx < 0 || W <= nx || ny < 0 || W <= ny) { continue; } int alt = dist[cur.v]; if (k == 0) { alt += x[cx][cy] ? 223 : 1000; } else if (k == 1) { alt += y[cx][cy] ? 223 : 1000; } else if (k == 2) { alt += x[nx][cy] ? 223 : 1000; } else { alt += y[cx][ny] ? 223 : 1000; } int next = toInt(nx, ny); if (alt < dist[next]) { dist[next] = alt; que.add(new Node(next, alt)); } } } int d = dist[o.cd]; int cnt = 0; while (d >= 0) { if (d % 1000 == 0) { break; } d -= 223; cnt++; } ret[i] = cnt; } return ret; } static int toInt(int x, int y) { return x * W + y; } static class Obj { int a, b, c, d, ab, cd; } static class Node implements Comparable { int v, d; public Node(int v, int d) { this.v = v; this.d = d; } public int compareTo(Node o) { return d - o.d; } } }