#include typedef long long ll; using namespace std; struct Boat{ ll x; ll y; ll l; ll id; char d; }; #define FULL 2 #define CORNER 1 #define WATER 0 vector isPlaced, visited; //aby lodka nebola na pozicii x, y bool placeBoat(Boat &b, vector> &arr, int x, int y, vector>> &placed){ if (isPlaced[b.id]) { return true; } isPlaced[b.id] = true; if (b.d == 'D') { for (int x2 : {b.x, b.x + b.l - 1}) { if (x2 != x) { if (arr[x2][b.y] == FULL) { return false; } else { arr[x2][b.y] = FULL; if (arr[x2][b.y] == CORNER) { for (Boat &otherBoat: placed[x2][b.y]) { if (!placeBoat(otherBoat, arr, x2, b.y, placed)) { return false; } } } } } } } else if (b.d == 'R') { for (int y2 : {b.y, b.y + b.l - 1}) { if (y2 != y) { if (arr[b.x][y2] == FULL){ return false; } else { arr[b.x][y2] = FULL; if (arr[b.x][y2] == CORNER) { for (Boat &otherBoat: placed[b.x][y2]) { if (!placeBoat(otherBoat, arr, b.x, y2, placed)) { return false; } } } } } } } return true; } pair dfs(Boat &boat, vector> &arr, int x, int y, vector>> &placed) { visited[boat.id] = true; int x2, y2; if (x == boat.x && y == boat.y) { if (boat.d == 'D') { x2 = boat.x + boat.l - 1; y2 = boat.y; } else { x2 = boat.x; y2 = boat.y + boat.l - 1; } } else { x2 = boat.x; y2 = boat.y; } ll boats = 1; ll collisions = 0; for (Boat &otherBoat : placed[x2][y2]) { if (!isPlaced[otherBoat.id]) { collisions++; } if (visited[otherBoat.id]) { continue; } auto rec = dfs(otherBoat, arr, x2, y2, placed); boats += rec.first; collisions += rec.second; } return {boats, collisions - 1}; } bool solve(){ ll h, w, n; cin >> h >> w >> n; isPlaced.resize(n); vector> arr(h, vector(w, 0)); vector>> placed(h, vector>(w)); for(ll i = 0; i < h; i++){ for(ll j = 0; j < w; j++) arr[i][j] = WATER; } vector boats; for(ll i = 0; i < n; i++){ ll x, y, l; char d; cin >> x >> y >> l >> d; x--; y--; if (d == 'U') { d = 'D'; x = x - l + 1; } else if (d == 'L') { d = 'R'; y = y - l + 1; } Boat b {x, y, l, i, d}; ll x2 = (d == 'D') ? x + l - 1 : x; ll y2 = (d == 'R') ? y + l - 1 : y; placed[x][y].push_back(b); if(arr[x][y] == WATER) { arr[x][y] = CORNER; } else if(arr[x][y] == FULL){ // umiestnit lod if (!placeBoat(b, arr, x, y, placed)) { return false; } } placed[x2][y2].push_back(b); if (arr[x2][y2] == WATER) { arr[x2][y2] = CORNER; } else if(arr[x2][y2] == FULL){ // druhy koniec if (!placeBoat(b, arr, x2, y2, placed)) { return false; } } ll xx, yy; if (!isPlaced[i]) { for(ll j = 1; j < l - 1; j++){ if(d == 'D'){ xx = x + j; yy = y; } else if (d == 'R') { xx = x; yy = y + j; } if (arr[xx][yy] == FULL){ return false; } if (arr[xx][yy] == CORNER) { arr[xx][yy] = FULL; for (Boat &otherBoat: placed[xx][yy]) { if (!placeBoat(otherBoat, arr, xx, yy, placed)) { return false; } } } arr[xx][yy] = FULL; } } } visited = vector(isPlaced); for(ll i = 0; i < h; i++){ for(ll j = 0; j < w; j++){ if (arr[i][j] == CORNER) { for (Boat &b: placed[i][j]) { if (!visited[b.id]) { auto res = dfs(b, arr, i, j, placed); //cout << res.first << " boats " << res.second << " collisions\n"; if (res.first < res.second) { return false; } } } } } } return true; } int main(){ bool res = solve(); cout << (res ? "Yes\n" : "No\n"); return 0; }