#line 1 "/home/maspy/compro/library/my_template.hpp" #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; using pi = pair; using vi = vector; using u32 = unsigned int; using u64 = unsigned long long; using i128 = __int128; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; template using pq = priority_queue; template using pqg = priority_queue, greater>; #define vec(type, name, ...) vector name(__VA_ARGS__) #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) // https://trap.jp/post/1224/ #define FOR1(a) for (ll _ = 0; _ < ll(a); ++_) #define FOR2(i, a) for (ll i = 0; i < ll(a); ++i) #define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i) #define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c)) #define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i) #define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i) #define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i) #define FOR4_R(i, a, b, c) for (ll i = (b)-1; i >= ll(a); i -= (c)) #define overload4(a, b, c, d, e, ...) e #define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define FOR_R(...) \ overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__) #define FOR_subset(t, s) for (ll t = s; t >= 0; t = (t == 0 ? -1 : (t - 1) & s)) #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second #define stoi stoll ll SUM(vector &A) { ll sum = 0; for (auto &&a: A) sum += a; return sum; } template T SUM(vector &A) { T sum = T(0); for (auto &&a: A) sum += a; return sum; } #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define LB(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()) int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template T pick(deque &que) { assert(que.size()); T a = que.front(); que.pop_front(); return a; } template T pick(pq &que) { assert(que.size()); T a = que.top(); que.pop(); return a; } template T pick(pqg &que) { assert(que.size()); T a = que.top(); que.pop(); return a; } template T pick(vc &que) { assert(que.size()); T a = que.back(); que.pop_back(); return a; } template T ceil(T x, U y) { return (x > 0 ? (x + y - 1) / y : x / y); } template T floor(T x, U y) { return (x > 0 ? x / y : (x - y + 1) / y); } template pair divmod(T x, U y) { T q = floor(x, y); return {q, x - q * y}; } ll binary_search(function check, ll ok, ll ng) { assert(check(ok)); while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; if (check(x)) ok = x; else ng = x; } return ok; } template double binary_search_real(F check, double ok, double ng, int iter = 100) { FOR(iter) { double x = (ok + ng) / 2; if (check(x)) { ok = x; } else { ng = x; } } return (ok + ng) / 2; } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } vi s_to_vi(const string &S, char first_char) { vi A(S.size()); FOR(i, S.size()) { A[i] = S[i] - first_char; } return A; } template vector cumsum(vector &A, int off = 1) { int N = A.size(); vector B(N + 1); FOR(i, N) { B[i + 1] = B[i] + A[i]; } if (off == 0) B.erase(B.begin()); return B; } template vc bincount(const vc &A, int size) { vc C(size); for (auto &&x: A) { ++C[x]; } return C; } template vector argsort(const vector &A) { // stable vector ids(A.size()); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); }); return ids; } // A[I[0]], A[I[1]], ... template vc rearrange(const vc &A, const vc &I) { int n = len(I); vc B(n); FOR(i, n) B[i] = A[I[i]]; return B; } #line 1 "/home/maspy/compro/library/other/io2.hpp" #define INT(...) \ int __VA_ARGS__; \ IN(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ IN(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ IN(__VA_ARGS__) #define DBL(...) \ long double __VA_ARGS__; \ IN(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ read(name) #define VV(type, name, h, w) \ vector> name(h, vector(w)); \ read(name) void read(int &a) { cin >> a; } void read(long long &a) { cin >> a; } void read(char &a) { cin >> a; } void read(double &a) { cin >> a; } void read(long double &a) { cin >> a; } void read(string &a) { cin >> a; } template void read(pair &p) { read(p.first), read(p.second); } template void read(vector &a) {for(auto &i : a) read(i);} template void read(T &a) { cin >> a; } void IN() {} template void IN(Head &head, Tail &...tail) { read(head); IN(tail...); } template ostream& operator<<(ostream& os, const pair& A) { os << A.fi << " " << A.se; return os; } template ostream& operator<<(ostream& os, const vector& A) { for (size_t i = 0; i < A.size(); i++) { if(i) os << " "; os << A[i]; } return os; } void print() { cout << "\n"; cout.flush(); } template void print(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(Tail)) cout << " "; print(forward(tail)...); } void YES(bool t = 1) { print(t ? "YES" : "NO"); } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { print(t ? "Yes" : "No"); } void No(bool t = 1) { Yes(!t); } void yes(bool t = 1) { print(t ? "yes" : "no"); } void no(bool t = 1) { yes(!t); } #line 3 "main.cpp" void solve() { LL(N, M); ll H = N, W = N; vv(int, G, H, W, -1); G[0][0] = 1; G[H - 1][W - 1] = 1; auto isin = [&](ll x, ll y) -> bool { return (0 <= x && x < H && 0 <= y && y < W); }; ll dx[] = {1, 0, -1, 0}; ll dy[] = {0, 1, 0, -1}; auto ask = [&](int a, int b) -> bool { if (G[a][b] != -1) return G[a][b]; print(1 + a, 1 + b); STR(S); G[a][b] = (S == "Black" ? 1 : 0); return G[a][b]; }; deque que; vv(int, dist, H, W, -1); auto add = [&](int x, int y, int d) -> void { if (ask(x, y) && dist[x][y] == -1) { dist[x][y] = d; que.eb(x, y); } }; add(0, 0, 0); while (len(que)) { auto [x, y] = pick(que); FOR(d, 4) { ll nx = x + dx[d], ny = y + dy[d]; if (isin(nx, ny)) add(nx, ny, dist[x][y] + 1); } } Yes(dist[H - 1][W - 1] != -1); } signed main() { cout << fixed << setprecision(15); ll T = 1; // LL(T); FOR(T) solve(); return 0; }