// Marcin Knapik Uwr1 // The codes may contain some pastes from: https://github.com/ShahjalalShohag/code-library #pragma GCC optimize "O3" #include using namespace std; #define sz(s) (int)s.size() #define f first #define s second #define pb push_back #define all(s) s.begin(), s.end() #define vi vector #define vvi vector #define ll long long #define ull unsigned ll #define vll vector #define vvll vector #define ii pair #define pll pair #define vii vector #define vvii vector #define viiii vector > const ll BIG_INF = 1e18; const int mod = 998244353; const int INF = 1e9 + 7; const int N = 1e6 + 7; // const int T = 1 << 20; #define ld long double template ostream & operator << (ostream&os, const pair & para) { os << para.first << ' ' << para.second; return os; } template ostream & operator << (ostream&os, const vector & vec){ for(int i = 0; i < sz(vec); i++) os << vec[i] << (i == sz(vec) - 1 ? "" : " "); return os; } template istream & operator >> (istream&is, vector & vec){ for(T & el : vec) is >> el; return is; } template istream & operator >> (istream&os, pair & para) { os >> para.first >> para.second; return os; } template void setmax(T & a, T b) {a = (a >= b ? a : b);} template void setmin(T & a, T b) {a = (a <= b ? a : b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define losuj(a, b) uniform_int_distribution(a, b)(rng) #define rep(i, n) for(int i = 0; i < n; i++) #define per(i, n) for(int i = n - 1; i >= 0; i--) int n; vector tab; vii king_moves; vii knight_moves; vii rook_moves; vii bish_moves; vii queen_moves; bool good(ii poz){ return poz.f >= 0 and poz.s >= 0 and poz.f < n and poz.s < n; } ii operator * (ii para, int x){ return {para.f * x, para.s * x}; } ii operator + (ii a, ii b){ return {a.f + b.f, a.s + b.s}; } vii moves(char piece, ii poz){ vii ret; if(piece == 'K'){ for(auto & u : king_moves){ ii new_poz = {poz + u}; if(good(new_poz)) ret.pb(new_poz); } } else if(piece == 'N'){ for(auto & u : knight_moves){ ii new_poz = {poz + u}; if(good(new_poz)) ret.pb(new_poz); } } else if(piece == 'R'){ for(auto & u : rook_moves){ for(int i = 1; i <= n; i++){ ii new_poz = {poz + u * i}; if(good(new_poz)) ret.pb(new_poz); } } } else if(piece == 'B'){ for(auto & u : bish_moves){ for(int i = 1; i <= n; i++){ ii new_poz = {poz + u * i}; if(good(new_poz)) ret.pb(new_poz); } } } else if(piece == 'Q'){ for(auto & u : queen_moves){ for(int i = 1; i <= n; i++){ ii new_poz = {poz + u * i}; if(good(new_poz)) ret.pb(new_poz); } } } return ret; } int id(ii pos){ return pos.f * n + pos.s; } int id(int a, int b){ return id({a, b}); } ii rev(int idik){ return {idik / n, idik % n}; } void prep(){ for(int i = -1; i <= 1; i++){ for(int j = -1; j <= 1; j++){ if(abs(i) + abs(j) == 2){ bish_moves.pb({i, j}); queen_moves.pb({i, j}); } else if(abs(i) + abs(j) == 1){ queen_moves.pb({i, j}); rook_moves.pb({i, j}); } if(abs(i) + abs(j)){ king_moves.pb({i, j}); } } } for(int i = -2; i <= 2; i++){ for(int j = -2; j <= 2; j++){ if(max(abs(i), abs(j)) != 2) continue; if(abs(i) + abs(j) == 3) knight_moves.pb({i, j}); } } } vvi G(N); viiii ans; vi vis(N); void dfs(int start){ vis[start] = true; for(auto & u : G[start]){ if(!vis[u]){ dfs(u); ans.pb({rev(u), rev(start)}); } } } void solve(){ char znak; cin >> n >> znak; tab = vector (n); cin >> tab; int ile = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(tab[i][j] == '.') continue; vii kroki = moves(tab[i][j], {i, j}); ile++; for(auto & u : kroki){ if(tab[u.f][u.s] == '.') continue; G[id(make_pair(i, j))].pb(id(u)); } } } bool found = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(tab[i][j] == '.') continue; dfs(id({i, j})); found = true; break; } if(found) break; } if(sz(ans) != ile - 1){ cout << "NO\n"; return; } cout << "YES\n"; for(auto & [a, b] : ans) cout << a.f + 1 << ' ' << a.s + 1 << ' ' << b.f + 1 << ' ' << b.s + 1 << '\n'; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); prep(); int test = 1; // cin >> test; for(int i = 1; i <= test; i++) solve(); return 0; }