import java.util.*; public class Main { Stick[] sticks; int n; int k; int[][] board; final Random random = new Random(0); final int inf = 1<<29; void solve() { Timer timer = new Timer(900); try (Scanner in = new Scanner(System.in)) { n = in.nextInt(); k = in.nextInt(); board = new int[n][n]; sticks = new Stick[k]; for (int i = 0; i < k; i++) { sticks[i] = new Stick(); sticks[i].len = in.nextInt(); sticks[i].placed = false; } for (int i = 0; i < n; i++) { String s = in.next(); for (int j = 0; j < n; j++) { board[i][j] = s.charAt(j) - '0'; } } } Stick[] sortedStick = sticks.clone(); Arrays.sort(sortedStick, Comparator.comparingInt(s -> -s.len)); for (Stick s : sortedStick) { put(s); } int iterate = 0; while ((iterate++&0xFF) != 0 || !timer.signal()) { int idx = random.nextInt(k); if (sticks[idx].placed) { if (random.nextInt(k) != 0) { move(sticks[idx]); } else { put(sticks[idx]); } } else { put(sticks[idx]); } } for (Stick s : sticks) { if (s.dir == 0) { // System.out.printf("%d %d %d %d\n", s.x+1, s.y+1, s.x+s.len, s.y+1); System.out.printf("%d %d %d %d\n", s.y+1, s.x+1, s.y+1, s.x+s.len); } else { // System.out.printf("%d %d %d %d\n", s.x+1, s.y+1, s.x+1, s.y+s.len); System.out.printf("%d %d %d %d\n", s.y+1, s.x+1, s.y+s.len, s.x+1); } } } void move(Stick s) { int d = random.nextInt(2); while (moveCost(s, d) <= 0) { if (s.dir == 0) { if (d == 0) { board[s.y][s.x-1+s.len] ^= 1; board[s.y][s.x-1] ^= 1; s.x -= 1; } else { board[s.y][s.x+s.len] ^= 1; board[s.y][s.x] ^= 1; s.x += 1; } } else { if (d == 0) { board[s.y-1+s.len][s.x] ^= 1; board[s.y-1][s.x] ^= 1; s.y -= 1; } else { board[s.y+s.len][s.x] ^= 1; board[s.y][s.x] ^= 1; s.y += 1; } } } } int moveCost(Stick s, int d) { if (s.dir == 0) { int x0 = s.x + 2*d-1; if (x0 < 0 || x0 + s.len - 1 >= n) return inf; if (d == 0) { return (board[s.y][s.x - 1] ^ 1) - board[s.y][s.x + s.len - 1]; } else { return (board[s.y][s.x + s.len] ^ 1) - board[s.y][s.x]; } } else { int y0 = s.y + 2*d-1; if (y0 < 0 || y0 + s.len - 1 >= n) return inf; if (d == 0) { return (board[s.y - 1][s.x] ^ 1) - board[s.y + s.len - 1][s.x]; } else { return (board[s.y + s.len][s.x] ^ 1) - board[s.y][s.x]; } } } void put(Stick s) { if (s.placed) { flip(s); } int opt = -inf; List place = new ArrayList<>(); for (int y = 0; y < n; y++) { int sum = 0; for (int x = 0; x < n; x++) { sum += board[y][x]; if (x >= s.len) sum -= board[y][x-s.len]; if (x >= s.len - 1) { if (opt < sum) { opt = sum; place.clear(); } if (opt == sum) { place.add((y*n+(x-s.len+1))*2+0); } } } } for (int x = 0; x < n; x++) { int sum = 0; for (int y = 0; y < n; y++) { sum += board[y][x]; if (y >= s.len) sum -= board[y-s.len][x]; if (y >= s.len - 1) { if (opt < sum) { opt = sum; place.clear(); } if (opt == sum) { place.add(((y-s.len+1)*n+x)*2+1); } } } } int p = place.get(random.nextInt(place.size())); s.x = p / 2 % n; s.y = p / 2 / n; s.dir = p % 2; // dump(s.x, s.y, s.dir, s.len, opt); flip(s); } void flip(Stick s) { if (s.dir == 0) { for (int dx = 0; dx < s.len; dx++) board[s.y][s.x+dx] ^= 1; } else { for (int dy = 0; dy < s.len; dy++) board[s.y+dy][s.x] ^= 1; } s.placed = !s.placed; } public static void main(String[] args) { new Main().solve(); } static void dump(Object... objects) { System.err.println(Arrays.deepToString(objects)); } class Stick { boolean placed; int x, y, dir, len; } class Timer { long start; long time; public Timer(long time) { this.start = System.currentTimeMillis(); this.time = time; } public void restart() { this.start = System.currentTimeMillis(); } public long elapsed() { return System.currentTimeMillis() - this.start; } public double scaled() { return (this.start + this.time - System.currentTimeMillis()) / (double) this.time; } public boolean signal() { return System.currentTimeMillis() >= this.start + this.time; } } }