import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) { watch.init(); try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { String line = br.readLine(); String[] split = line.split(" "); int N = Integer.parseInt(split[0]); int K = Integer.parseInt(split[1]); line = br.readLine(); split = line.split(" "); int[] L = new int[K]; for (int i = 0; i < K; i++) { L[i] = Integer.parseInt(split[i]); } int[][] A = new int[N][N]; for (int r = 0; r < N; r++) { line = br.readLine(); for (int c = 0; c < N; c++) { A[r][c] = line.charAt(c) - '0'; } } String[] ret = new Main().run(N, K, L, A); for (int i = 0; i < ret.length; ++i) { System.out.println(ret[i]); } System.out.flush(); } catch (Exception e) { e.printStackTrace(); } } private double score; private double bestScore; static final XorShift rng = new XorShift(System.nanoTime()); static final Watch watch = new Watch(); private SAState sa = new SAState(); private int N; private int K; private int[] L; private int[][] A; private int W0; private boolean[] isVerticals; private int[] rs; private int[] cs; private boolean[] bestIsVerticals; private int[] bestRs; private int[] bestCs; private String[] run(int N, int K, int[] L, int[][] A) { init(N, K, L, A); greedy(); SA(); return makeSolution(); } private void greedy() { for (int k = 0; k < K; k++) { isVerticals[k] = rng.nextDouble() < 0.5; if (isVerticals[k]) { rs[k] = (int) ((N - L[k]) * rng.nextDouble()); cs[k] = (int) (N * rng.nextDouble()); } else { rs[k] = (int) (N * rng.nextDouble()); cs[k] = (int) ((N - L[k]) * rng.nextDouble()); } flip(k, isVerticals[k], rs[k], cs[k]); } } private String[] makeSolution() { String[] result = new String[K]; for (int k = 0; k < K; k++) { if (isVerticals[k]) { result[k] = "" + (rs[k] + 1) + " " + (cs[k] + 1) + " " + (rs[k] + 1 + (L[k] - 1)) + " " + (cs[k] + 1); } else { result[k] = "" + (rs[k] + 1) + " " + (cs[k] + 1) + " " + (rs[k] + 1) + " " + (cs[k] + 1 + (L[k] - 1)); } } return result; } private void init(int n, int k, int[] l, int[][] a) { N = n; K = k; L = l; A = a; isVerticals = new boolean[K]; rs = new int[K]; cs = new int[K]; bestIsVerticals = new boolean[K]; bestRs = new int[K]; bestCs = new int[K]; W0 = 0; W0 = calculateScore(a); Utils.debug("init", "time", watch.getSecondString()); } private int calculateScore(int[][] a) { int W = 0; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (a[r][c] == 0) { W++; } } } return W - W0; } private void SA() { score = calculateScore(A); bestScore = -1e99; saveBest(); sa.startTime = watch.getSecond(); sa.endTime = 0.9; sa.init(); for (;; sa.numIterations++) { if ((sa.numIterations & ((1 << 10) - 1)) == 0) { sa.update(); if (sa.isTLE()) { loadBest(); Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%7.2f", score), String.format("%7.2f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature)); break; } } mutate(); } Utils.debug("SA", "time", watch.getSecondString()); } private void mutate() { random(); } private void random() { int k = (int) (K * rng.nextDouble()); boolean currentIsVertical = isVerticals[k]; int currentR = rs[k]; int currentC = cs[k]; boolean newIsVertical = rng.nextDouble() < 0.5; int newR = currentR + (int) (-sa.range * 0.5 + sa.range * rng.nextDouble()); int newC = currentC + (int) (-sa.range * 0.5 + sa.range * rng.nextDouble()); if (newIsVertical) { newR = Math.min(Math.max(newR, 0), N - L[k] - 1); newC = Math.min(Math.max(newC, 0), N - 1); } else { newR = Math.min(Math.max(newR, 0), N - 1); newC = Math.min(Math.max(newC, 0), N - L[k] - 1); } double deltaScore = 0; if (currentIsVertical) { for (int l = 0; l < L[k]; l++) { if (A[currentR + l][currentC] == 0) { deltaScore--; } else { deltaScore++; } } } else { for (int l = 0; l < L[k]; l++) { if (A[currentR][currentC + l] == 0) { deltaScore--; } else { deltaScore++; } } } if (newIsVertical) { for (int l = 0; l < L[k]; l++) { if (isIntersect(newR + l, newC, currentR, currentC, currentR + (currentIsVertical ? L[k] - 1 : 0), currentC + (currentIsVertical ? 0 : L[k] - 1))) { if (A[newR + l][newC] == 0) { deltaScore++; } else { deltaScore--; } } else { if (A[newR + l][newC] == 1) { deltaScore++; } else { deltaScore--; } } } } else { for (int l = 0; l < L[k]; l++) { if (isIntersect(newR, newC + l, currentR, currentC, currentR + (currentIsVertical ? L[k] - 1 : 0), currentC + (currentIsVertical ? 0 : L[k] - 1))) { if (A[newR][newC + l] == 0) { deltaScore++; } else { deltaScore--; } } else { if (A[newR][newC + l] == 1) { deltaScore++; } else { deltaScore--; } } } } if (sa.accept(deltaScore)) { score += deltaScore; flip(k, currentIsVertical, currentR, currentC); flip(k, newIsVertical, newR, newC); isVerticals[k] = newIsVertical; rs[k] = newR; cs[k] = newC; saveBest(); } else { } } private boolean isIntersect(int r, int c, int minR, int minC, int maxR, int maxC) { return r >= minR && r <= maxR && c >= minC && c <= maxC; } private void flip(int k, boolean isVertical, int r, int c) { if (isVertical) { for (int l = 0; l < L[k]; l++) { A[r + l][c] ^= 1; } } else { for (int l = 0; l < L[k]; l++) { A[r][c + l] ^= 1; } } } private void saveBest() { if (score > bestScore) { bestScore = score; for (int k = 0; k < K; k++) { bestIsVerticals[k] = isVerticals[k]; bestRs[k] = rs[k]; bestCs[k] = cs[k]; } } } private void loadBest() { score = bestScore; for (int k = 0; k < K; k++) { isVerticals[k] = bestIsVerticals[k]; rs[k] = bestRs[k]; cs[k] = bestCs[k]; } } } class SAState { public static final boolean useTime = true; public double startTime = 0; public double endTime = 9.5; public double time = startTime; public double startTemperature = 1; public double endTemperature = 0; public double inverseTemperature = 1.0 / startTemperature; public double lastAcceptTemperature = startTemperature; public double startRange = 31; public double endRange = 3; public double range = startRange; public int numIterations; public int validIterations; public int acceptIterations; public void init() { numIterations = 0; validIterations = 0; acceptIterations = 0; startTime = useTime ? Main.watch.getSecond() : numIterations; update(); lastAcceptTemperature = inverseTemperature; } public void update() { updateTime(); updateTemperature(); updateRange(); } public void updateTemperature() { inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0)); } public void updateRange() { range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0); } public void updateTime() { time = useTime ? Main.watch.getSecond() : numIterations; } public boolean isTLE() { return time >= endTime; } public boolean accept(double deltaScore) { return acceptB(deltaScore); } public boolean acceptB(double deltaScore) { validIterations++; if (deltaScore > -1e-9) { acceptIterations++; return true; } assert deltaScore < 0; assert 1.0 / inverseTemperature >= 0; if (deltaScore * inverseTemperature < -10) { return false; } if (Main.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } public boolean acceptS(double deltaScore) { validIterations++; if (deltaScore < 1e-9) { acceptIterations++; return true; } assert deltaScore > 0; assert 1.0 / inverseTemperature >= 0; if (-deltaScore * inverseTemperature < -10) { return false; } if (Main.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } } final class Utils { private Utils() { } public static final void debug(Object... o) { System.err.println(toString(o)); } public static final String toString(Object... o) { return Arrays.deepToString(o); } } class Watch { private long start; public Watch() { init(); } public double getSecond() { return (System.nanoTime() - start) * 1e-9; } public void init() { init(System.nanoTime()); } private void init(long start) { this.start = start; } public String getSecondString() { return toString(getSecond()); } public static final String toString(double second) { if (second < 60) { return String.format("%5.2fs", second); } else if (second < 60 * 60) { int minute = (int) (second / 60); return String.format("%2dm%2ds", minute, (int) (second % 60)); } else { int hour = (int) (second / (60 * 60)); int minute = (int) (second / 60); return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60)); } } } class XorShift { private int w = 88675123; private int x = 123456789; private int y = 362436069; private int z = 521288629; public XorShift(long l) { x = (int) l; } public int nextInt() { final int t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >>> 19) ^ (t ^ (t >>> 8)); return w; } public long nextLong() { return ((long) nextInt() << 32) ^ (long) nextInt(); } public double nextDouble() { return (nextInt() >>> 1) * 4.6566128730773926E-10; } public int nextInt(int n) { return (int) (n * nextDouble()); } }