Đề bài

Để sáng tác một bài thi cho CEOI 2024, Ben được hội đồng khoa học tặng một món đồ chơi. Đó là một trò xếp hình có thể hình dung như một lưới \(H\times W\), bên trong có một vật bằng kim loại gồm hai phần: một thanh ngang kích thước \(1\times K\) và một thanh dọc kích thước \(L\times 1\), được gắn lỏng với nhau.

Không thanh nào có thể xoay theo bất kỳ cách nào, nhưng mỗi thanh có thể trượt theo chiều dọc hoặc chiều ngang độc lập với thanh còn lại, miễn là chúng luôn chồng lên nhau tại đúng một ô.

Ngoài ra, lưới còn chứa một số chướng ngại vật. Không thanh nào của vật kim loại có thể đi xuyên qua chướng ngại vật. Các thanh cũng không thể đi ra ngoài lưới, kể cả chỉ một phần. Nhiệm vụ của Ben là di chuyển vật kim loại từ vị trí bắt đầu được chỉ định đến một vị trí có thể khác sao cho cả hai thanh chồng lên ô đích được chỉ định.

Tuy nhiên, Ben đã chơi món đồ này một lúc mà vẫn chưa giải được. Thực tế, cậu bắt đầu nghi rằng ban tổ chức đã trêu mình và đưa cho cậu một trò xếp hình không thể giải. Vì vậy, cậu nhờ bạn xác định liệu trò xếp hình có giải được hay không.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(W\), \(H\), \(K\), \(L\), cách nhau bởi dấu cách, lần lượt là chiều rộng và chiều cao của trò xếp hình, chiều rộng của thanh ngang và chiều cao của thanh dọc.

Dòng thứ hai chứa bốn số nguyên \(x_h\), \(y_h\), \(x_v\), \(y_v\). Hai số đầu là tọa độ của ô ngoài cùng bên trái bị thanh ngang chiếm, hai số sau là tọa độ của ô trên cùng bị thanh dọc chiếm.

Các hàng được đánh số từ \(0\) đến \(H-1\) theo thứ tự từ trên xuống dưới; các cột được đánh số từ \(0\) đến \(W-1\) theo thứ tự từ trái sang phải. Tọa độ \(x\) là số cột và tọa độ \(y\) là số hàng.

\(H\) dòng tiếp theo, mỗi dòng gồm \(W\) ký tự, biểu diễn lưới:

• . biểu diễn một ô trống.
• X biểu diễn một chướng ngại vật.
• * biểu diễn ô đích.

Dữ liệu bảo đảm vị trí ban đầu của vật kim loại là hợp lệ: hai thanh chồng lên nhau tại đúng một ô, không thanh nào chồng lên chướng ngại vật hoặc nhô ra ngoài lưới.

Trên lưới có đúng một ô đích, tức là ký tự * xuất hiện đúng một lần. Ô đích có thể nằm dưới vật kim loại ở vị trí ban đầu.

Dữ liệu ra

In một dòng chứa YES nếu có thể di chuyển vật kim loại đến ô đích; ngược lại, in NO.

Giới hạn

• \(2\le W,H\le 1\,500\).
• \(2\le K\le W\) và \(2\le L\le H\).
• \(0\le x_h\le W-K\) và \(0\le y_h\le H-1\).
• \(0\le x_v\le W-1\) và \(0\le y_v\le H-L\).

Chấm điểm

• Subtask 1 (14 điểm): \(W,H\le 50\).
• Subtask 2 (21 điểm): \(W,H\le 90\).
• Subtask 3 (9 điểm): \(W,H\le 300\) và \(K,L\le 10\).
• Subtask 4 (29 điểm): \(W,H\le 360\).
• Subtask 5 (27 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 3 2 2
0 1 0 0
.X.*
....
...X

YES

2 3 2 3
0 1 0 0
.X
.*
.X

NO