#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end()) typedef long long ll; typedef long double ld; typedef pair P; typedef complex comp; typedef vector< vector > matrix; struct pairhash { public: template size_t operator()(const pair &x) const { size_t seed = hash()(x.first); return hash()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }; const int inf = 1e9 + 9; const ll mod = 1e9 + 7; const double eps = 1e-8; const double pi = acos(-1); int n, k; int l[500]; bool a[60][60]; bool b[60][60]; struct timeval t1, t2; double get_elapsed_time(struct timeval *begin, struct timeval *end) { return (end->tv_sec - begin->tv_sec) * 1000 + (end->tv_usec - begin->tv_usec) / 1000.0; } class Pos { public: int d, y, x; Pos(int d, int y, int x): d(d), y(y), x(x) {} }; unsigned long xor128(void) { static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } // [0, k) int rand(int k) { return xor128() % k; } void solve() { vector vec; for (int i = 0; i < k; i++) { int d = rand(2); if (d) vec.push_back(Pos(d, rand(n-l[i]), rand(n))); else vec.push_back(Pos(d, rand(n), rand(n-l[i]))); } for (int i = 0; i < k; i++) { Pos p = vec[i]; int dy = (p.d==0 ? 1 : l[i]); int dx = (p.d==1 ? 1 : l[i]); for (int y = p.y; y < p.y+dy; y++) { for (int x = p.x; x < p.x+dx; x++) { b[y][x] ^= 1; } } } int cnt = 0; while (true) { int idx = rand(k); int d = rand(2); int Y = (d==0 ? rand(n) : rand(n-l[idx])); int X = (d==1 ? rand(n) : rand(n-l[idx])); int dy = (d==0 ? 1 : l[idx]); int dx = (d==1 ? 1 : l[idx]); Pos p = vec[idx]; int pdy = (p.d==0 ? 1 : l[idx]); int pdx = (p.d==1 ? 1 : l[idx]); int dif = 0; for (int y = p.y; y < p.y+pdy; y++) { for (int x = p.x; x < p.x+pdx; x++) { b[y][x] ^= 1; dif += 1-2*(a[y][x]^b[y][x]); } } for (int y = Y; y < Y+dy; y++) { for (int x = X; x < X+dx; x++) { b[y][x] ^= 1; dif += 1-2*(a[y][x]^b[y][x]); } } if (dif < 0) { for (int y = p.y; y < p.y+pdy; y++) { for (int x = p.x; x < p.x+pdx; x++) b[y][x] ^= 1; } for (int y = Y; y < Y+dy; y++) { for (int x = X; x < X+dx; x++) b[y][x] ^= 1; } } else { //cerr << dif << endl; vec[idx] = Pos(d, Y, X); } cnt++; if (cnt % 1000 == 0) { gettimeofday(&t2, NULL); if (get_elapsed_time(&t1, &t2) > 980) break; } } for (int i = 0; i < k; i++) { int dy = (vec[i].d==0 ? 0 : l[i]-1); int dx = (vec[i].d==1 ? 0 : l[i]-1); cout << vec[i].y+1 << " " << vec[i].x+1 << " " << vec[i].y+dy+1 << " " << vec[i].x+dx+1 << endl; } } void input() { gettimeofday(&t1, NULL); cin >> n >> k; for (int i = 0; i < k; i++) cin >> l[i]; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < n; j++) a[i][j] = (bool)(s[j]-'0'); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); input(); solve(); }