#include using namespace std; using lld = long long; using int128 = __int128_t; struct T { int a,b; }; struct Graph { vector path; bool vis = false; }; vector res; void dfs(vector& g, int v) { g[v].vis = true; for(int u : g[v].path) if(!g[u].vis) { res.push_back({u,v}); dfs(g,u); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; char k; cin >> n >> k; vector t(n); for(auto& i : t) cin >> i; vector pos; vector g(n*n); for(int i=0;i=0;a++,b--) if(t[a][b] != '.') g[a*n+b].path.push_back(i*n+j); for(int a=i-1,b=j+1;a>=0 && b=0 && b>=0;a--,b--) if(t[a][b] != '.') g[a*n+b].path.push_back(i*n+j); break; case 'Q': for(int a=i+1,b=j+1;a=0;a++,b--) if(t[a][b] != '.') g[a*n+b].path.push_back(i*n+j); for(int a=i-1,b=j+1;a>=0 && b=0 && b>=0;a--,b--) if(t[a][b] != '.') g[a*n+b].path.push_back(i*n+j); for(int x=0;x