import java.io.IOException; import java.util.Scanner; /** * yukicoder * * @author tsukammo */ public class Main { Scanner sc = new Scanner(System.in); Random rnd = new Random(19881221L); long st, et; int first; public static void main(String[] args) throws IOException { new Main().solve(); } // 制約 static int N = 60, K = 500, NN = N * N, W = 25; int[] L; boolean[][] map; Rect[] rs; void solve() { input(); init(); simulate(); // new if (submit) { output(); } } void init() { rs = new Rect[K]; for (int i = 0; i < K; i++) { rs[i] = new Rect(i, L[i] - 1); } if (submit) { return; } } void simulate() { System.err.println("First:" + (first)); int score = evalAll(); System.err.println("Start:" + (score)); long currentTime = System.currentTimeMillis(); double C = TEMP * TL; double Line = 0.0; int tmpScore = 0; int c = 0, u = 0; while (currentTime < et) { if (c % 1000 == 0) { currentTime = System.currentTimeMillis(); Line = (et - currentTime) / C; } c++; int id = rnd.nextInt(K); Rect r = rs[id]; int d = rnd.nextInt(2); int x, y; if (d == 0) { x = rnd.nextInt(N - r.w); y = rnd.nextInt(N); } else { x = rnd.nextInt(N); y = rnd.nextInt(N - r.w); } int ex = x + r.w * dx[d]; int ey = y + r.w * dy[d]; tmpScore = evalChange(x, y, d, r); if (tmpScore <= 0 || Line > tmpScore * rnd.nextDouble()) { score += tmpScore; // update r.x = x; r.y = y; r.d = d; if (tmpScore < 0) { u++; } //System.err.println("update:" + score); } else { // rollback // before ex = r.x; ey = r.y; for (int i = 0; i <= r.w; i++) { map[ey][ex] = !map[ey][ex]; ex += dx[r.d]; ey += dy[r.d]; } // after ex = x; ey = y; for (int i = 0; i <= r.w; i++) { map[ey][ex] = !map[ey][ex]; ex += dx[d]; ey += dy[d]; } } } System.err.println("End :" + (score)); score = evalAll(); System.err.println("End :" + (score)); System.err.println("Last :" + (first - score) + " loop:" + c + " up:" + u); } int evalChange(int x, int y, int d, Rect r) { int ret = 0; // before int ex = r.x; int ey = r.y; for (int i = 0; i <= r.w; i++) { if (map[ey][ex]) { ret--; } else { ret++; } map[ey][ex] = !map[ey][ex]; ex += dx[r.d]; ey += dy[r.d]; } // after ex = x; ey = y; for (int i = 0; i <= r.w; i++) { if (map[ey][ex]) { ret--; } else { ret++; } map[ey][ex] = !map[ey][ex]; ex += dx[d]; ey += dy[d]; } return ret; } int evalAll() { int ret = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (map[i][j]) { ret++; } } } return ret; } final static int dx[] = new int[] { 1, 0, -1, 0 }; final static int dy[] = new int[] { 0, 1, 0, -1 }; boolean outMap(int x, int y) { return !(x > -1 && y > -1 && x < N && y < N); } void input() { N = sc.nextInt(); st = System.currentTimeMillis(); et = st + TL; K = sc.nextInt(); L = new int[K]; for (int i = 0; i < K; i++) { L[i] = sc.nextInt(); } sc.nextLine(); map = new boolean[N][N]; first = 0; for (int i = 0; i < N; i++) { String tmp = sc.nextLine(); char[] cl = tmp.toCharArray(); for (int j = 0; j < N; j++) { if (cl[j] == '1') { map[i][j] = true; first++; } } } } class Rect { int id; int x, y, d; int w; public Rect(int id, int w) { this.id = id; this.w = w; this.x = rnd.nextInt(N); this.y = rnd.nextInt(N); this.d = rnd.nextInt(4); int ex = x + w * dx[d]; int ey = y + w * dy[d]; if (outMap(ex, ey)) { if (outMap(ex, ey)) { if (d > 1) { d -= 2; } else { d += 2; } } } ex = x; ey = y; // flip for (int i = 0; i <= w; i++) { map[ey][ex] = !map[ey][ex]; ex += dx[d]; ey += dy[d]; } } public String toString() { int sx = x + 1; int sy = y + 1; int ex = sx + w * dx[d]; int ey = sy + w * dy[d]; if (d > 1) { sx = ex; sy = ey; d -= 2; ex = sx + w * dx[d]; ey = sy + w * dy[d]; } return sy + " " + sx + " " + ey + " " + ex; } } class Random { private long seed; private final long multiplier = 0x5DEECE66DL, addend = 0xBL, mask = (1L << 48) - 1; int bits, val; Random(long seed) { this.seed = seed; } int nextInt(int n) { do { bits = (int) ((seed = (seed * multiplier + addend) & mask) >>> 17); val = bits % n; } while (bits - val + (n - 1) < 0); return val; } double nextDouble() { return nextInt(10000000) / 10000000.0; } } void output() { for (int i = 0; i < K; i++) { System.out.println(rs[i].toString()); } } final double TEMP = 10000; static final long TL = 800; static boolean submit = true; }