#include #include #include #include #include #include #include #include #include #include #include #include #include #include using ll = long long; enum : int { M = (int)1e9 + 7 }; enum : ll { MLL = (ll)1e18L + 9 }; using namespace std; #ifdef LOCAL #include"rprint2.hpp" #include"debug_deque.hpp" #define vector DebugDeque #else #define FUNC(name) template void name(T&&...){ } FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde); #endif template istream& operator >> (istream& in, pair& p){ in >> p.first >> p.second; return in; } template istream& operator >> (istream& in, vector& v){ for(auto& e : v){ in >> e; } return in; } #define LIMIT 0.9 mt19937 mt; timeval start; double elapsed(){ timeval now; gettimeofday(&now, nullptr); return (now.tv_sec - start.tv_sec) + (now.tv_usec - start.tv_usec) / 1e6; } struct Ans { int a, b, c, d; friend ostream& operator << (ostream& out, Ans& e) { return out << e.a + 1 << ' ' << e.b + 1 << ' ' << e.c + 1 << ' ' << e.d + 1; } }; int main(){ gettimeofday(&start, nullptr); cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; vector ls(k); cin >> ls; vector as(n); cin >> as; for(auto& a : as){ for(auto& e : a){ e -= '0'; } } vector ans(k); // vector> ps(k); // for(int i = 0; i < k; i++){ // ps[i] = {ls[i], i}; // } // sort(ps.rbegin(), ps.rend()); // for(auto p : ps){ // int i = p.second; for(int i = 0; i < k; i++){ int maxi = -1; for(int y = 0; y < n; y++){ for(int x = 0; x < n - ls[i]; x++){ int cnt = 0; for(int j = 0; j < ls[i]; j++){ cnt += as[y][x + j]; } if(maxi < cnt){ maxi = cnt; ans[i] = {y, x, y, x + ls[i] - 1}; } } } for(int y = 0; y < n - ls[i]; y++){ for(int x = 0; x < n; x++){ int cnt = 0; for(int j = 0; j < ls[i]; j++){ cnt += as[y + j][x]; } if(maxi < cnt){ maxi = cnt; ans[i] = {y, x, y + ls[i] - 1, x}; } } } for(int y = ans[i].a; y <= ans[i].c; y++){ for(int x = ans[i].b; x <= ans[i].d; x++){ as[y][x] = !as[y][x]; } } } while(elapsed() < LIMIT){ for(int _ = 0; _ < 100; _++){ // for(elapsed() < LIMIT){ for(int i = 0; i < 100; i++){ int i = mt() % k; if(ans[i].a == ans[i].c){ while(ans[i].d + 1 < n && as[ans[i].a][ans[i].b] && as[ans[i].a][ans[i].d + 1]){ as[ans[i].a][ans[i].b] = !as[ans[i].a][ans[i].b]; as[ans[i].a][ans[i].d + 1] = !as[ans[i].a][ans[i].d + 1]; ans[i].b++; ans[i].d++; } while(ans[i].b && as[ans[i].a][ans[i].b - 1] && as[ans[i].a][ans[i].d]){ as[ans[i].a][ans[i].b - 1] = !as[ans[i].a][ans[i].b - 1]; as[ans[i].a][ans[i].d] = !as[ans[i].a][ans[i].d]; ans[i].b--; ans[i].d--; } } if(ans[i].b == ans[i].d){ while(ans[i].c + 1 < n && as[ans[i].a][ans[i].b] && as[ans[i].c + 1][ans[i].b]){ as[ans[i].a][ans[i].b] = !as[ans[i].a][ans[i].b]; as[ans[i].c + 1][ans[i].b] = !as[ans[i].c + 1][ans[i].b]; ans[i].a++; ans[i].c++; } while(ans[i].a && as[ans[i].a - 1][ans[i].b] && as[ans[i].c][ans[i].b]){ as[ans[i].a - 1][ans[i].b] = !as[ans[i].a - 1][ans[i].b]; as[ans[i].c][ans[i].b] = !as[ans[i].c][ans[i].b]; ans[i].a--; ans[i].c--; } } } } for(auto& e : ans){ cout << e << '\n'; } }