#include using namespace std; __attribute__((always_inline)) bool present(int val) { return val != INT_MAX; } template __attribute__((always_inline)) void process (T_Unio& uniox, int N, int idx, int i, int j, int idx2, int i2, int j2) { assert(idx == i*N+j); assert(idx2 == i2*N+j2); assert(i >= 0 && i < N && j >= 0 && j < N); if (i2 >= 0 && i2 < N && j2 >= 0 && j2 < N) { uniox(idx, idx2); } } int holvan(std::vector& T, int i) { assert(present(T[i])); if (T[i] < 0) { return i; } return T[i] = holvan(T, T[i]); } bool rek(std::vector>&G, int N, int a, int d) { // if (volte[a]) { // return false; // } // volte[a] = true; for (int b: G[a]) { if (b == d) { continue; } if (rek(G, N, b, a)) { int i0,j0,i1,j1; i0 = b/N; j0 = b%N; i1 = a/N; j1 = a%N; cout << i0+1 << " " << j0+1 << " " << i1+1 << " " << j1+1 << "\n"; } } return true; } int main() { int N; cin >> N; char strategy = '.'; { string strategy_s; cin >> strategy_s; strategy = strategy_s[0]; } vector T(N*N, INT_MAX); for (int i = 0; i < N; i++) { string line; cin >> line; for (int j = 0; j < N; j++) { char c = line[j]; if (c != '.') { T[i*N+j] = -1; } } } const auto unio = [&T](int idx0, int idx1) { assert(present(T[idx0]) && present(T[idx1])); int holvan0 = holvan(T,idx0); int holvan1 = holvan(T,idx1); if (holvan0 == holvan1) { return false; } if (T[holvan0] < T[holvan1]) { T[holvan0] += T[holvan1]; T[holvan1] = holvan0; } else { T[holvan1] += T[holvan0]; T[holvan0] = holvan1; } return true; }; vector> G(N*N); const auto uniox = [&unio, &G, &T](int idx0, int idx1) { assert(present(T[idx0])); if (present(T[idx1])) { if (unio(idx0, idx1)) { G[idx0].push_back(idx1); G[idx1].push_back(idx0); } } }; int idx = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { assert(i*N+j == idx); int c = T[idx]; if (present(c)) { if (strategy == 'K') { int dx = -1, dy = -1; for (int k = 0; k < 9; k++) { #define PROC(dx, dy) process(uniox, N, idx, i, j, idx + dx*N+dy, i+dx, j+dy) if (dx != 0 || dy != 0) { PROC(dx, dy); } dx++; if (dx == 2) { dx = -1; dy++; } } } if (strategy == 'Q' || strategy == 'B') { for (int k = -N+1; k < N; k++) { if (k == 0) { continue; } PROC(+k, -k); PROC(+k, +k); } } if (strategy == 'Q' || strategy == 'R') { for (int k = 0; k < N; k++) { if (k == 0) { continue; } PROC(+k, 0); PROC(0, +k); } } if (strategy == 'N') { assert(strategy == 'N'); PROC(+2, -1); PROC(+2, +1); PROC(+1, -2); PROC(+1, +2); PROC(-1, -2); PROC(-1, +2); PROC(-2, +1); PROC(-2, -1); } } idx++; } } int nRoots = 0; for (int i = 0; i < N*N; i++) { if (present(i)) { if (T[i] < 0) { nRoots++; } } } if (nRoots > 1) { cout << "NO\n"; return 0; } cout << "YES\n"; for (int i = 0; i < N; i++) { if (present(T[i])) { rek(G, N, i, -1); return 0; } } return 0; }