#include using ll = long long int; #define fr(i, x) for(ll i = 0; i < x; ++i) using namespace std; ll N; char figure; char grid[100][100]; ll pair_to_ll(ll x, ll y){ return x * N + y; } pair ll_to_pair(ll a){ return {a/N, a % N}; } vector> graph; void add_reepadlo(vector> & to, ll x, ll y){ for(int i = x-1; i >= 0; --i ){ if(grid[x][i] != '.'){ to.push_back({x, i}); break; } } for(int i = x+1; i < N; ++i ){ if(grid[x][i] != '.'){ to.push_back({x, i}); break; } } for(int i = y-1; i >= 0; --i ){ if(grid[i][y] != '.'){ to.push_back({i, y}); break; } } for(int i = y+1; i < N; ++i ){ if(grid[i][y] != '.'){ to.push_back({i, y}); break; } } } void add_bugger(vector> & to, ll x, ll y){ for(int i = 1; i < N; ++i){ if(grid[x +i][y+i] != '.'){ to.push_back({x+i, y+i}); break; } } for(int i = 1; i < N; ++i){ if(grid[x +i][y-i] != '.'){ to.push_back({x+i, y-i}); break; } } for(int i = 1; i < N; ++i){ if(grid[x -i][y+i] != '.'){ to.push_back({x-i, y+i}); break; } } for(int i = 1; i < N; ++i){ if(grid[x -i][y-i] != '.'){ to.push_back({x-i, y-i}); break; } } } vector> get_neighbours(ll x, ll y){ vector> result; switch(figure){ case 'K': result ={ {x+1, y-1}, {x+1, y}, {x+1, y+1}, {x, y-1}, {x, y+1}, {x-1, y-1}, {x-1, y}, {x-1, y+1} }; break; case 'N': result ={ {x+2, y-1}, {x+2, y+1}, {x+1, y+2}, {x+1, y-2}, {x-1, y+2}, {x-1, y-2}, {x-2, y-1}, {x-2, y+1} }; break; case 'R': add_reepadlo(result, x, y); break; case 'B': add_bugger(result, x, y); break; case 'Q': add_reepadlo(result, x, y); add_bugger(result, x, y); break; } vector> result2; for(const pair & p : result){ if(p.first < N && p.first >= 0 && p.second < N && p.second >= 0){ result2.push_back(p); } } return result2; } vector> get_figures(){ vector> result; fr(i, N)fr(j, N){ if(grid[i][j] != '.'){ result.push_back({i, j}); } } return result; } vector> childs; bool is_connected(unordered_set points){ int first = *points.begin(); queue q; q.push(first); points.erase(first); while (!q.empty()){ ll c = q.front(); q.pop(); for(ll neigh : graph[c]){ if(points.count(neigh) == 1){ points.erase(neigh); q.push(neigh); childs[c].push_back(neigh); } } } return points.size() == 0; } void construct_graph(vector> figures){ for(const pair & p : figures){ vector> neigh = get_neighbours(p.first, p.second); ll x = pair_to_ll(p.first, p.second); for(const pair & q : neigh){ ll y = pair_to_ll(q.first, q.second); graph[x].push_back(y); graph[y].push_back(x); } } } void print_postfix(ll current, ll father){ for(ll child : childs[current]){ print_postfix(child, current); } if(father != -1){ pair me = ll_to_pair(current); pair papa = ll_to_pair(father); cout << me.first +1 << " " << me.second + 1 << " " << papa.first + 1 << " " << papa.second + 1 << endl; } } int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> figure; graph = vector>(N*N); childs = vector>(N*N); fr(i, N)fr(j, N){ cin >> grid[i][j]; } vector> figures = get_figures(); unordered_set set_figures; construct_graph(figures); for(const pair & p : figures){ ll llfigure = pair_to_ll(p.first, p.second); set_figures.insert(llfigure); } if(!is_connected(set_figures)){ cout << "NO" << endl; return 0; } cout << "YES" << endl; ll root = *set_figures.begin(); print_postfix(root, -1); return 0; }