#include using namespace std; using ll = long long; using ld = long double; using pii = pair; using vi = vector; using vvi = vector; #define rep(i, a, b) for(ll i = (a); i < (b); i++) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() struct mo { ll x1, y1, x2, y2; mo(ll x1, ll y1, ll x2, ll y2) : x1(x1), y1(y1), x2(x2), y2(y2) {} }; void solve() { ll r, c; cin >> r >> c; vector> from(r, vector(c)), to(r, vector(c)); rep(i, 0, r) rep(ii, 0, c) cin >> from[i][ii]; rep(i, 0, r) rep(ii, 0, c) cin >> to[i][ii]; pii single_overlap = make_pair(-1, -1); rep(i, 0, r) rep(ii, 0, c) if (from[i][ii] == '*' && to[i][ii] == '*') { single_overlap = make_pair(i, ii); }; auto adj = [&](ll i, ll ii) { vector next; if (i + 1 < r) next.emplace_back(i+1, ii); if (ii + 1 < c) next.emplace_back(i, ii+1); if (i - 1 >= 0) next.emplace_back(i-1, ii); if (ii - 1 >= 0) next.emplace_back(i, ii-1); return next; }; auto getOrdering = [&](vector& start, vector>& map) { vector> seen(r, vector(c, false)); for(auto [x, y] : start) seen[x][y] = true; rep(i, 0, sz(start)) { auto [x1, y1] = start[i]; for (auto [x2, y2] : adj(x1, y1)) if (!seen[x2][y2] && map[x2][y2] == '*') { seen[x2][y2] = true; start.emplace_back(x2, y2); } } }; auto markOverlap = [&](pii& start, vector>& marked) { marked[start.first][start.second] = true; queue todo; for(todo.push(start); sz(todo); todo.pop()) { auto [x1, y1] = todo.front(); for (auto [x2, y2] : adj(x1, y1)) if (!marked[x2][y2] && from[x2][y2] == '*' && to[x2][y2] == '*') { marked[x2][y2] = true; todo.emplace(x2, y2); } } }; if (single_overlap.first == -1) { queue start; vector> prev(r, vector(c, make_pair(-1, -1))); rep(i, 0, r) rep(ii, 0, c) if(from[i][ii] == '*') { start.emplace(i, ii); prev[i][ii].first = -2; } pii attachEnd, attachStart; bool foundEnd = false; for(; sz(start); start.pop()) { auto [i, ii] = start.front(); if (to[i][ii] == '*') { attachEnd = make_pair(i, ii); foundEnd = true; break; } for (auto [x, y] : adj(i, ii)) if (prev[x][y].first == -1 && from[x][y] != 'X'){ prev[x][y] = make_pair(i, ii); start.emplace(x, y); } } if (!foundEnd) { cout << "NO" << endl; return; } vector path(1, attachEnd); while(from[path.back().first][path.back().second] != '*') { path.push_back(prev[path.back().first][path.back().second]); } attachStart = path.back(); path.pop_back(); reverse(all(path)); path.pop_back(); vector fromOrdering; fromOrdering.push_back(attachStart); getOrdering(fromOrdering, from); vector toOrdering; toOrdering.push_back(attachEnd); getOrdering(toOrdering, to); reverse(all(fromOrdering)); fromOrdering.insert(end(fromOrdering), all(path)); path.insert(end(path), all(toOrdering)); assert(sz(fromOrdering) == sz(path)); cout << "YES" << endl; cout << sz(fromOrdering) << endl; rep(i, 0, sz(fromOrdering)) { cout << fromOrdering[i].first + 1 << " " << fromOrdering[i].second + 1 << " " << path[i].first + 1 << " " << path[i].second + 1 << endl; } } else { vector> marked(r, vector(c, false)); markOverlap(single_overlap, marked); vector overlap; rep(i, 0, r) rep(ii, 0, c) if (marked[i][ii]) overlap.emplace_back(i, ii); vector fromOrdering(all(overlap)), toOrdering(all(overlap)); getOrdering(fromOrdering, from); getOrdering(toOrdering, to); fromOrdering.erase(begin(fromOrdering), next(begin(fromOrdering), sz(overlap))); toOrdering.erase(begin(toOrdering), next(begin(toOrdering), sz(overlap))); reverse(all(fromOrdering)); vector moves; auto fromIter = begin(fromOrdering); auto toIter = begin(toOrdering); while(fromIter != end(fromOrdering)) { moves.emplace_back(fromIter->first, fromIter->second, toIter->first, toIter->second); from[fromIter->first][fromIter->second] = '.'; from[toIter->first][toIter->second] = '*'; markOverlap(*toIter, marked); while(toIter != end(toOrdering) && marked[toIter->first][toIter->second]) toIter++; do { fromIter++; } while(fromIter != end(fromOrdering) && marked[fromIter->first][fromIter->second]); } if (toIter != end(toOrdering)) exit(0); // NO-OUTPUT cout << "YES" << endl; cout << sz(moves) << endl; for(auto [x1, y1, x2, y2] : moves) { cout << x1 + 1 << " " << y1 + 1 << " " << x2 + 1 << " " << y2 + 1 << endl; } } } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); //ll t; cin >> t; while(t--) solve(); }