#include using namespace std; #define fwd(i, a, n) for (int i = (a); i < (n); i ++) #define rep(i, n) fwd(i, 0, n) #define all(X) begin(X), end(X) #define sz(X) ((int)X.size()) #define st first #define nd second #define pii pair #define vi vector #define ll long long #ifdef LOC auto &operator<<(auto &out, pair a) { return out << "(" << a.st << ", " << a.nd << ")"; } auto &operator<<(auto &out, auto a) { out << "{"; for (auto b : a) out << b << ", "; return out << "}"; } void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; } #define debug(x...) cerr << __LINE__ << " [" #x "]: ", dump(x) #else #define debug(...) 0 #endif int r, c; const pii NONE{-1, -1}; vector oldbody, newbody; vector vis; vector dfsorder; vector> par; pii fcommon() { rep(i, r) rep(j, c) if (oldbody[i][j] == '*' && newbody[i][j] == '*') return {i, j}; return NONE; } void dodfs(int i, int j, vector &body) { // debug(i, j, body, vis); if (i < 0 || i >= r || j < 0 || j >= c || body[i][j] != '*' || vis[i][j]) return; // debug(1); vis[i][j] = true; // debug(1); dfsorder.push_back({i, j}); // debug(1); dodfs(i-1, j, body); dodfs(i+1, j, body); dodfs(i, j-1, body); dodfs(i, j+1, body); } pii pardfs(int i, int j) { // debug(__LINE__); if (par[i][j] == NONE) par[i][j] = {i, j}; // debug(__LINE__); if (newbody[i][j] == '*') return {i, j}; // debug(__LINE__); for (auto [x, y] : {pii{i-1, j}, {i+1, j}, {i, j-1}, {i, j+1}}) { // debug(x, y); if (x < 0 || x >= r || y < 0 || y >= c || par[x][y] != NONE) continue; if (oldbody[x][y] == '*' || oldbody[x][y] == 'X') continue; par[x][y] = {i, j}; auto ret = pardfs(x, y); if (ret != NONE) return ret; } return NONE; } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> r >> c; oldbody.resize(r); newbody.resize(r); rep(i, r) cin >> oldbody[i]; rep(i, r) cin >> newbody[i]; vector addq, remq; pii common = fcommon(); if (common == NONE) { par.assign(r, vector(c, NONE)); rep(i, r) rep(j, c) if (oldbody[i][j] == '*') { if (sz(addq)) continue; pii endq = pardfs(i, j); if (endq == NONE) continue; vector path = {endq}; while (true) { pii prv = par[path.back().first][path.back().second]; if (prv == path.back()) break; path.push_back(prv); } path.erase(path.begin()); path.pop_back(); // reverse(all(path)); debug("hard", path); dfsorder.clear(); vis.assign(r, vi(c, 0)); dodfs(i, j, oldbody); remq = vector(dfsorder.rbegin(), dfsorder.rend()); for (auto x : path) remq.push_back(x); dfsorder.clear(); vis.assign(r, vi(c, 0)); dodfs(endq.first, endq.second, newbody); addq = vector(dfsorder.begin(), dfsorder.end()); for (auto x : path) addq.insert(addq.begin(), x); } } else { debug("easy", common); dfsorder.clear(); vis.assign(r, vi(c, 0)); debug(r, c, common); dodfs(common.first, common.second, oldbody); debug(__LINE__); remq = vector(dfsorder.rbegin(), dfsorder.rend()); debug(__LINE__); dfsorder.clear(); vis.assign(r, vi(c, 0)); dodfs(common.first, common.second, newbody); debug(__LINE__); addq = vector(dfsorder.begin(), dfsorder.end()); debug(__LINE__); } if (addq.empty()) { cout << "NO\n"; return 0; } auto curr = oldbody; reverse(all(addq)); reverse(all(remq)); debug(addq); debug(remq); vector> ops; while (sz(addq)) { auto add = addq.back(); addq.pop_back(); auto rem = remq.back(); remq.pop_back(); if (add == rem) continue; if (curr[add.first][add.second] == '*') { remq.push_back(rem); remq.erase(find(all(remq), add)); continue; } assert(curr[add.first][add.second] == '.'); assert(curr[rem.first][rem.second] == '*'); curr[add.first][add.second] = '*'; curr[rem.first][rem.second] = '.'; ops.emplace_back(rem, add); } cout << "YES\n"; cout << sz(ops) << '\n'; for (auto [ij, xy] : ops) { auto [i, j] = ij; auto [x, y] = xy; cout << i+1 << ' ' << j+1 << ' ' << x+1 << ' ' << y+1 << '\n'; } return 0; }