#include #define REP(i, n) for (int i = 0; (i) < int(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i)) #define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= int(m); -- (i)) #define ALL(x) begin(x), end(x) #define dump(x) cerr << #x " = " << x << endl #define unittest_name_helper(counter) unittest_ ## counter #define unittest_name(counter) unittest_name_helper(counter) #define unittest __attribute__((constructor)) void unittest_name(__COUNTER__) () using ll = long long; using namespace std; template using reversed_priority_queue = priority_queue, greater >; template inline void chmax(T & a, T const & b) { a = max(a, b); } template inline void chmin(T & a, T const & b) { a = min(a, b); } template auto vectors(X x, T a) { return vector(x, a); } template auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector(x, cont); } template ostream & operator << (ostream & out, vector const & xs) { REP (i, int(xs.size()) - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; } int count_black(int y, int x, bool is_vertical, int len, vector > const & a) { if (is_vertical) { int cnt = 0; REP (i, len) cnt += a[y + i][x]; return cnt; } else { return count(a[y].begin() + x, a[y].begin() + (x + len), true); } } void apply_rect(int y, int x, bool is_vertical, int len, vector > & a) { REP (i, len) { int ny = y + (is_vertical ? i : 0); int nx = x + (is_vertical ? 0 : i); auto && p = a[ny][nx]; p = not p; } } vector > solve(int n, int k, vector const & l, vector > a) { vector > lookup(n + 1); REP (i, k) lookup[l[i]].push_back(i); vector > result(k); REP_R (len, n + 1) { for (int i : lookup[len]) { int highscore = -1; REP (y, n) REP (x, n) REP (is_vertical, 2) { if ( is_vertical and y + len > n) continue; if (not is_vertical and x + len > n) continue; int score = count_black(y, x, is_vertical, l[i], a); if (highscore < score) { highscore = score; result[i] = make_tuple(y, x, is_vertical); } } assert (highscore != -1); int y, x; bool is_vertical; tie(y, x, is_vertical) = result[i]; apply_rect(y, x, is_vertical, l[i], a); } } int white = 0; REP (y, n) white += count(ALL(a[y]), false); cerr << "white = " << white << " / " << n * n << endl; return result; } int main() { // input int n, k; cin >> n >> k; vector l(k); REP (i, k) cin >> l[i]; auto a = vectors(n, n, bool()); REP (y, n) REP (x, n) { char c; cin >> c; a[y][x] = c - '0'; } // solve vector > result = solve(n, k, l, a); // output REP (i, k) { int y, x; bool is_vertical; tie(y, x, is_vertical) = result[i]; int ny = y + (is_vertical ? l[i] - 1 : 0); int nx = x + (is_vertical ? 0 : l[i] - 1); cout << y + 1 << ' ' << x + 1 << ' ' << ny + 1 << ' ' << nx + 1 << endl; } return 0; }