import java.io.*; import java.util.*; public class Main implements Runnable { static ContestScanner in; static Writer out; public static void main(String[] args) { new Thread(null, new Main(), "", 16 * 1024 * 1024).start(); } public void run() { Main main = new Main(); try { in = new ContestScanner(); out = new Writer(); main.solve(); out.close(); in.close(); } catch (IOException e) { e.printStackTrace(); } } int[] l, lt; long[] mask; int[] lx, ly, ld; long[][] map; int n, k; void solve() throws IOException { genTestIO(); sa(); output(); // solveByTest(); } void solveByTest() { int sum = 0; for (int i = 0; i < 32; i++) { genTest(i); int res = solveGreedy() + sa(); sum += res; System.out.println(res); } System.out.println("Score: " + sum); // output(); // for (int i = 0; i < n; i++) { // for (int j = 0; j < n; j++) { // System.out.print((map[i][0] >> j) & 1); // System.out.print(" "); // } // System.out.println(); // } } void output() { for (int i = 0; i < k; i++) { final int idx = lt[i]; if(ld[idx] == 0) out.println(String.format("%d %d %d %d", ly[idx] + 1, lx[idx] + 1, ly[idx] + 1, lx[idx] + l[idx])); else out.println(String.format("%d %d %d %d", ly[idx] + 1, lx[idx] + 1, ly[idx] + l[idx], lx[idx] + 1)); } } void genTest(long seed) { boolean debug = false; Random rand = new Random(seed); n = 60; k = 500; l = new int[k]; lt = new int[k]; lx = new int[k]; ly = new int[k]; ld = new int[k]; mask = new long[k]; Pair[] p = new Pair[k]; if (debug) out.println(n + " " + k); for (int i = 0; i < k; i++) { l[i] = rand.nextInt(25) + 1; p[i] = new Pair(-l[i], i); if (debug) { if (i > 0) out.print(" "); out.print(l[i]); } } Arrays.sort(p); for (int i = 0; i < k; i++) { l[i] = -p[i].a; mask[i] = (1L << l[i]) - 1; lt[p[i].b] = i; } if (debug) out.println(); map = new long[n][2]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { long a = rand.nextInt(2); map[i][0] |= a << j; map[j][1] |= a << i; if (debug)out.print(a); } if (debug)out.println(); } } void genTestIO() throws IOException { n = in.nextInt(); k = in.nextInt(); l = new int[k]; lt = new int[k]; lx = new int[k]; ly = new int[k]; ld = new int[k]; mask = new long[k]; for (int i = 0; i < k; i++) { l[i] = in.nextInt(); lt[i] = i; mask[i] = (1L << l[i]) - 1; } map = new long[n][2]; for (int i = 0; i < n; i++) { char[] s = in.nextToken().toCharArray(); for (int j = 0; j < n; j++) { long a = s[j] - '0'; map[i][0] |= a << j; map[j][1] |= a << i; } } } int solveGreedy() { int cnt = 0; for (int i = 0; i < k; i++) { int max = Integer.MIN_VALUE; int maxPos = 0; int maxV = 0; for (int j = 0; j < n; j++) { for (int m = 0; m < n - l[i]; m++) { for (int d = 0; d < 2; d++) { int res = check(d, j, m, i, map); if (res > max) { max = res; maxPos = j * n + m; maxV = d; } } } } cnt += max; setLPos(maxV, maxPos / n, maxPos % n, i); apply(maxV, maxPos / n, maxPos % n, i, map); } return cnt; } /** * @param v 縦横 * @param y y座標(実際のもの) * @param x x座標(実際のもの) * @param id 利用する棒のid */ void applyReal(int v, int y, int x, int id, long[][] map) { if (v == 1) apply(v, x, y, id, map); else apply(v, y, x, id, map); } void apply(int v, int y, int x, int id, long[][] map) { map[y][v] ^= mask[id] << x; for (int i = 0; i < l[id]; i++) { map[i + x][v^1] ^= 1L << y; } } void setLPos(int v, int y, int x, int id) { if (v == 1) { int tmp = y; y = x; x = tmp; } ld[id] = v; ly[id] = y; lx[id] = x; } int checkReal(int v, int y, int x, int id, long[][] map) { if (v == 1) return check(v, x, y, id, map); else return check(v, y, x, id, map); } int check(int v, int y, int x, int id, long[][] map) { return Long.bitCount(map[y][v]) - Long.bitCount(map[y][v] ^ (mask[id] << x)); } int checkDoubleReal(int v, int y1, int x1, int y2, int x2, int id, long[][] map) { if (v == 1) return checkDouble(v, x1, y1, x2, y2, id, map); else return checkDouble(v, y1, x1, y2, x2, id, map); } int checkDouble(int v, int y1, int x1, int y2, int x2, int id, long[][] map) { if (y1 == y2) { return Long.bitCount(map[y1][v]) - Long.bitCount(map[y1][v] ^ (mask[id] << x1) ^ (mask[id] << x2)); } else { return check(v, y1, x1, id, map) + check(v, y2, x2, id, map); } } int tld, tly, tlx, tid; int next(Random rand, int vol) { tid = rand.nextInt(k); int score; if (rand.nextDouble() < 0.01) { tld = ld[tid] ^ 1; tlx = lx[tid]; tly = ly[tid]; if (tld == 0) { if (lx[tid] + l[tid] >= n) tlx = n - l[tid]; } else { if (ly[tid] + l[tid] >= n) tly = n - l[tid]; } final long cp = (map[ly[tid]][0] >> lx[tid]) & 1; score = checkReal(ld[tid], ly[tid], lx[tid], tid, map) + checkReal(tld, tly, tlx, tid, map) + (cp == 1 ? -2 : 2); } else { final int mvol = rand.nextInt(vol) + 1; final int yvol = rand.nextInt(mvol); final int xvol = mvol - yvol; int minY = Math.max(0, ly[tid] - yvol); final int maxY = Math.min(n - (ld[tid] == 0 ? 1 : l[tid]), ly[tid] + yvol); minY = Math.min(minY, maxY); tly = rand.nextInt(maxY - minY + 1) + minY; int minX = Math.max(0, lx[tid] - xvol); final int maxX = Math.min(n - (ld[tid] == 0 ? l[tid] : 1), lx[tid] + xvol); minX = Math.min(minX, maxX); tlx = rand.nextInt(maxX - minX + 1) + minX; score = checkDoubleReal(ld[tid], ly[tid], lx[tid], tly, tlx, tid, map); tld = ld[tid]; } return score; } void applyNext() { applyReal(ld[tid], ly[tid], lx[tid], tid, map); ld[tid] = tld; ly[tid] = tly; lx[tid] = tlx; applyReal(ld[tid], ly[tid], lx[tid], tid, map); } double temper(double r) { return Math.pow(TEMPER, r); } double prob(double nextScore, double temper) { if(0 <= nextScore) return 1; else return Math.pow(Math.E, nextScore / temper); } final double TEMPER = 0.15; int sa() { final int MAX_ITER = 1500000; Random rand = new Random(0); int score = 0;//init(rand); for (int i = 0; i < MAX_ITER; i++) { int vol = Math.max(1, (MAX_ITER - i) * 20 / MAX_ITER); int nextScore = next(rand, vol); double temperature = temper((double) i / MAX_ITER); double prob = prob(nextScore, temperature); if(rand.nextDouble() <= prob) { score += nextScore; applyNext(); } } return score; } int init(Random rand) { int score = 0; for (int i = 0; i < k; i++) { ld[i] = rand.nextInt(2); final int maxY = n - (ld[i] == 0 ? 1 : l[i]); final int maxX = n - (ld[i] == 0 ? l[i] : 1); ly[i] = rand.nextInt(maxY + 1); lx[i] = rand.nextInt(maxX + 1); score += checkReal(ld[i], ly[i], lx[i], i, map); applyReal(ld[i], ly[i], lx[i], i, map); } return score; } } class Pair implements Comparable { int a, b; Pair(int a, int b) { this.a = a; this.b = b; } @Override public int compareTo(Pair o) { if (a != o.a) return a - o.a; return b - o.b; } } class Writer extends PrintWriter{ public Writer(String filename)throws IOException {super(new BufferedWriter(new FileWriter(filename)));} public Writer()throws IOException {super(System.out);} } class ContestScanner implements Closeable { private BufferedReader in;private int c=-2; public ContestScanner()throws IOException {in=new BufferedReader(new InputStreamReader(System.in));} public ContestScanner(String filename)throws IOException {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));} public String nextToken()throws IOException { StringBuilder sb=new StringBuilder(); while((c=in.read())!=-1&&Character.isWhitespace(c)); while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();} return sb.toString(); } public String readLine()throws IOException{ StringBuilder sb=new StringBuilder();if(c==-2)c=in.read(); while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();} return sb.toString(); } public long nextLong()throws IOException,NumberFormatException {return Long.parseLong(nextToken());} public int nextInt()throws NumberFormatException,IOException {return(int)nextLong();} public double nextDouble()throws NumberFormatException,IOException {return Double.parseDouble(nextToken());} public void close() throws IOException {in.close();} }