// #pragma GCC optimize("Ofast") // #pragma GCC target("sse4") #include using namespace std; #define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME #define __FOR3(i, a, n, inc) for(int i = (a); (inc) > 0 ? i < (n) : i >= (n); i += (inc)) #define __FOR2(i, a, n) __FOR3(i, a, n, 1) #define __FOR1(i, n) __FOR2(i, 0, n) #define __FOR0(n) __FOR1(_, n) #define FOR(...) GET_MACRO(__VA_ARGS__, __FOR3, __FOR2, __FOR1, __FOR0)(__VA_ARGS__) #define BOOST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ELO exit(0) #define ALL(a) (a).begin(), (a).end() #define SZ(a) (int)(a).size() #define TRAV(a, b) for (auto& a : b) #define REV(a) reverse(ALL(a)) #define SORT(a) sort(ALL(a)) #define SORTR(a) SORT(a), REV(a) #define PB push_back #define F first #define S second using ll = long long; using ld = long double; // 'long double' is 2.2 times slower than double using pii = pair; using pll = pair; using pld = pair; using vb = vector; using vi = vector; using vvi = vector; using vll = vector; using vvll = vector; using vpii = vector; using vpll = vector; using vld = vector; using vpld = vector; constexpr int MOD = 1e9 + 7; // 998244353 constexpr int INF = MOD; constexpr ll LLINF = 1e18; const ld PI = acos(-1); template inline bool setmin(T& a, T b) {if (a > b) return a = b, 1; return 0; } template inline bool setmax(T& a, T b) {if (a < b) return a = b, 1; return 0; } namespace input { template istream &operator>>(istream &os, vector & vec) { for (auto& u : vec) os >> u; return os; } template istream& operator>>(istream& os, pair& p) { return os >> p.first >> p.second; } template istream& operator>>(istream& os, array& a) { for (auto& u : a) os >> u; return os; } void re() {} template void re(T& x, args&... tail) { cin >> x; re(tail...); } } // namespace input using namespace input; namespace output { template ostream &operator<<(ostream &os, const vector & vec){for (const auto& u : vec) os << u << " "; return os; } template ostream& operator<<(ostream& os, const pair& p) { return os << p.first << " " << p.second; } template ostream &operator<<(ostream &os, set & con) { for (const auto& u : con) os << u << " "; return os; } template ostream& operator<<(ostream& os, array& a) { for (const auto& u : a) os << u << " "; return os; } void pr() {} template void pr(const T& x) { cout << x; } template void pr(const T& x, const args&... tail) { cout << x << " "; pr(tail...);} template void prs(const T& x) { cout << x << " "; } template void prs(const T& x, const args&... tail) { cout << x << " "; prs(tail...);} template void prln(const args&... tail) { pr(tail...); cout << "\n";} } // namespace output using namespace output; namespace pair_magic { #define PT1T2 pair #define TT1T2 template TT1T2 inline PT1T2 operator+(const PT1T2 &p1, const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); } TT1T2 inline PT1T2& operator+=(PT1T2 &p1, const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; } TT1T2 inline PT1T2 operator-(const PT1T2 &p1, const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); } TT1T2 inline PT1T2& operator-=(PT1T2 &p1, const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; } #undef PT1T2 #undef TT1T2 } using namespace pair_magic; namespace random_nsp { thread_local std::mt19937 gen{std::random_device{}()}; template T random(T min, T max){using dist = std::conditional_t::value, std::uniform_int_distribution, std::uniform_real_distribution>;return dist{min, max}(gen);} template T randomINT(T min, T max) { return std::uniform_int_distribution{min, max}(gen); } } using namespace random_nsp; namespace triple { #define TT1T2T3 template #define TRT1T2T3 triple TT1T2T3 struct triple { T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c) {} }; TT1T2T3 bool operator<(const TRT1T2T3&t1, const TRT1T2T3&t2) { if (t1.a != t2.a)return t1.a < t2.a; else if (t1.b != t2.b)return t1.b < t2.b; else return t1.c < t2.c; } TT1T2T3 bool operator>(const TRT1T2T3&t1, const TRT1T2T3&t2) { if (t1.a != t2.a)return t1.a > t2.a; else if (t1.b != t2.b)return t1.b > t2.b; else return t1.c > t2.c; } TT1T2T3 bool operator==(const TRT1T2T3&t1, const TRT1T2T3&t2) { return (t1.a == t2.a && t1.b == t2.b && t1.c == t2.c); } TT1T2T3 inline istream& operator >> (istream& os, triple& t) { return os >> t.a >> t.b >> t.c; } TT1T2T3 ostream& operator << (ostream& os, const triple& t) { return os << t.a << " " << t.b << " " << t.c; } #undef TRT1T2T3 #undef TT1T2T3 using tri = triple; using trll = triple; using vtri = vector; using vtrll = vector; } using namespace triple; template T invGeneral(T a, T b) { // 0 < a < b, gcd(a,b) = 1 a %= b; if (a == 0) return b == 1 ? 0 : -1; T x = invGeneral(b, a); return x == -1 ? -1 : ((1-(ll)b * x) / a + b) % b; } template struct modular { T val; explicit operator T() const { return val; } modular() { val = 0; } modular(const ll& v) { val = (-MOD <= v && v <= MOD) ? v : v % MOD; if (val < 0) val += MOD; } friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; } friend void pr(const modular& a) { pr(a.val); } friend void re(modular& a) { ll x; re(x); a = modular(x); } friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; } friend bool operator!=(const modular& a, const modular& b) { return !(a == b); } friend bool operator<(const modular& a, const modular& b) { return a.val < b.val; } modular operator-() const { return modular(-val); } modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; } modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; } modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; } friend modular pow(modular a, ll p) { modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a; return ans; } friend modular inv(const modular& a) { auto i = invGeneral(a.val,MOD); assert(i != -1); return i; } // equivalent to return exp(b,MOD-2) if MOD is prime modular& operator/=(const modular& m) { return (*this) *= inv(m); } friend modular operator+(modular a, const modular& b) { return a += b; } friend modular operator-(modular a, const modular& b) { return a -= b; } friend modular operator*(modular a, const modular& b) { return a *= b; } friend modular operator/(modular a, const modular& b) { return a /= b; } }; using mi = modular; using pmi = pair; using vmi = vector; using vpmi = vector; namespace debug { template < typename _T > inline void _debug(const char *s, _T x) { cerr << s << " = " << x << "\n"; } template < typename _T, typename... args > void _debug(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _debug(s + 1, a...); } #if defined(LOCAL) && 1 #define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__) #define cerr cout #else #define debug(...) 1999 #define cerr if(0) cout #endif } // namespace debug using namespace debug; ///____________CODE____________/// const int N = 100 + 7; char grid[N][N]; int n; char type; vpii graf[N][N]; void add(int x, int y, int nx, int ny) { if (0 <= nx and nx < n and 0 <= ny and ny < n) { if (grid[nx][ny] != '.') { graf[x][y].PB({nx, ny}); } } } void make(int x, int y, char type) { if (type == 'N') { const int dx[8]{2, -2, 2, -2, 1, 1, -1, -1}; const int dy[8]{1, 1, -1, -1, 2, -2, 2, -2}; FOR(d, 8) { int nx = x + dx[d], ny = y + dy[d]; add(x, y, nx, ny); } return; } if (type == 'K') { FOR(dx, -1, 2) FOR(dy, -1, 2) { if (dx != 0 or dy != 0) { add(x, y, x + dx, y + dy); } } return; } if (type == 'R' or type == 'Q') { const int dx[4]{1, -1, 0, 0}; const int dy[4]{0, 0, 1, -1}; FOR(d, 4) { FOR(i, 1, n) { add(x, y, x + dx[d] * i, y + dy[d] * i); } } } if (type == 'B' or type == 'Q') { const int dx[4]{1, 1, -1, -1}; const int dy[4]{1, -1, 1, -1}; FOR(d, 4) { FOR(i, 1, n) { add(x, y, x + dx[d] * i, y + dy[d] * i); } } } } bool vis[N][N]; pii parent[N][N]; vector> result; int dfs(int x, int y) { int res = 1; vis[x][y] = true; parent[x][y] = {-1, -1}; TRAV(s, graf[x][y]) { int nx = s.F, ny = s.S; if (not vis[nx][ny]) { res += dfs(nx, ny); result.PB({{nx, ny}, {x, y}}); } } return res; } int main() { BOOST; re(n, type); FOR(i, n) FOR(j, n) re(grid[i][j]); FOR(i, n) { FOR(j, n) { if (grid[i][j] == type) { make(i, j, type); } } } int cnt = 0; FOR(i, n) FOR(j, n) cnt += grid[i][j] == type; debug(cnt); if (cnt == 0) { prln("YES"); ELO; } FOR(i, n) FOR(j, n) if(grid[i][j] == type) { int temp = dfs(i, j); debug(temp); if (temp != cnt) { prln("NO"); ELO; } prln("YES"); TRAV(i, result) { prln(i.F.F + 1, i.F.S + 1, i.S.F + 1, i.S.S + 1); } ELO; } }