Bạn đang cố gắng đánh cắp một chiếc vương miện kim cương vô cùng giá trị từ bảo tàng. Điều khiến nó trở nên hấp dẫn là (do cắt giảm ngân sách) tất cả các bảo vệ đã được thay thế bằng một máy bay không người lái (drone) tự động tuần tra sảnh chính của bảo tàng. Tuy nhiên, điều khiến nó bớt hấp dẫn hơn là chiếc drone này được trang bị một số vũ khí rất hiện đại và bạn có khả năng sẽ bị tiêu diệt nếu thu hút sự chú ý của nó.
May mắn thay, bạn đã chuẩn bị kỹ lưỡng và nắm khá rõ cách thức hoạt động của drone. Hãy tưởng tượng sảnh là một mặt phẳng Euclid, được chia thành các ô vuông đơn vị. Ô trung tâm, $(0, 0)$, chứa vương miện. Drone có một bộ xử lý đơn giản lưu trữ hai thứ: vị trí hiện tại $(x, y)$ và chuỗi hướng dẫn, được ký hiệu bằng các chữ cái 'N', 'E', 'S', 'W'. Mỗi phút, drone di chuyển đến một vị trí liền kề theo chữ cái đầu tiên của chuỗi (Bắc, Nam, Tây hoặc Đông), thay đổi vị trí đã lưu tương ứng, sau đó chuyển chữ cái đầu tiên này xuống cuối chuỗi để truy cập chữ cái tiếp theo vào phút sau. Nếu chuỗi hướng dẫn trống, drone đơn giản là không làm gì cả. Đảm bảo rằng các hướng dẫn này mô tả một vòng lặp khép kín và drone không bao giờ đi vào ô $(0, 0)$.
Hiện tại, drone đang ở vị trí $(x_0, y_0)$ và có một chuỗi hướng dẫn $T$. Bạn có thể sửa đổi bộ nhớ của drone bằng một số thủ thuật hack thông minh – mục tiêu của bạn là đạt đến tình huống mà drone ở cùng vị trí $(x_0, y_0)$, nhưng với chuỗi hướng dẫn khác là $T'$. Chiến lược hack của bạn, thật không may, có phần hạn chế – mỗi phút, bạn chỉ có thể truy cập hai chữ cái đầu tiên của chuỗi và thực hiện bất kỳ số lượng thao tác nào sau đây:
- xóa hai chữ cái đầu tiên khỏi chuỗi, nhưng chỉ khi chúng là "NS", "SN", "EW" hoặc "WE";
- thêm hai chữ cái "NS", "SN", "EW" hoặc "WE" vào đầu chuỗi;
- hoán đổi hai chữ cái đầu tiên của chuỗi (bất kỳ sự kết hợp nào của các chữ cái đều có thể được hoán đổi).
Ngoài ra, có một hệ thống phát hiện va chạm được triển khai trên drone, hệ thống này phát hiện xem tập hợp hướng dẫn hiện tại có khả năng đưa drone đến $(0, 0)$ hay không. Một báo động sẽ được kích hoạt trong trường hợp này – đây là tình huống bạn muốn tránh bằng mọi giá.
Hãy tìm một chuỗi các thao tác hack sẽ đưa drone đến $(x_0, y_0)$ với chuỗi mong muốn $T'$ trong bộ nhớ của nó.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào bao gồm một số duy nhất $z$ ($1 \le z \le 100$), biểu thị số lượng bộ dữ liệu kiểm tra. Các mô tả của các bộ dữ liệu kiểm tra theo sau.
Dòng đầu tiên của mỗi bộ dữ liệu kiểm tra bao gồm hai số nguyên $x_0, y_0$ ($-1000 \le x_0, y_0 \le 1000$), biểu thị vị trí ban đầu của drone. Ít nhất một trong các số $x_0, y_0$ khác không.
Dòng thứ hai chứa hai số $n, m$ ($2 \le n, m \le 2000$) – độ dài của chuỗi hiện tại ($T$) và chuỗi mục tiêu ($T'$) tương ứng.
Hai dòng tiếp theo chứa mỗi dòng một chuỗi, có độ dài lần lượt là $n$ và $m$, biểu thị $T$ và $T'$, chỉ bao gồm các chữ cái N, S, E và W.
Đảm bảo rằng các chuỗi hiện tại và mục tiêu là khác nhau. Hơn nữa, cả hai đều mô tả một số vòng lặp khép kín và không có vòng lặp nào trong số đó đi qua $(0, 0)$ tại bất kỳ thời điểm nào của lộ trình.
Tổng số chữ cái trong tất cả các bộ dữ liệu kiểm tra không vượt quá $20\,000$.
Dữ liệu ra
Đối với mỗi bộ dữ liệu kiểm tra, nếu không thể đáp ứng các yêu cầu của bài toán, hãy xuất "NO" trên một dòng duy nhất. Nếu không, hãy xuất "YES", và sau đó là mô tả giải pháp trên dòng tiếp theo. Giải pháp phải chỉ bao gồm các ký hiệu $\{N, S, E, W, -, R, C\}$, trong đó mỗi ký tự biểu thị một thao tác hack đơn lẻ:
- Ký hiệu 'N' có nghĩa là thêm "NS" vào đầu chuỗi.
- Tương tự, các ký hiệu 'S', 'E' và 'W' có nghĩa là thêm "SN", "EW" và "WE" vào đầu chuỗi.
- Ký hiệu 'R' có nghĩa là xóa hai chữ cái đầu tiên khỏi chuỗi – điều này chỉ được phép nếu các chữ cái này là "NS", "SN", "EW" hoặc "WE".
- Ký hiệu 'C' có nghĩa là hoán đổi hai chữ cái đầu tiên.
- Ký hiệu '-' có nghĩa là bạn đợi trong phần còn lại của phút (cho đến khi drone di chuyển đến hướng dẫn tiếp theo).
Lưu ý rằng nhiều thao tác hack có thể được thực hiện trong một phút. Bạn không cần phải tối thiểu hóa độ dài giải pháp, nhưng mô tả hành động không được có quá $2 \cdot 10^7$ ký tự. Đến cuối phút cuối cùng của đầu ra, chuỗi và vị trí của drone phải khớp với các giá trị mong muốn. Việc xóa hoặc hoán đổi các phần tử của một chuỗi có tối đa một chữ cái là không được phép. Tại bất kỳ thời điểm nào, vòng lặp được mô tả bởi chuỗi của drone không được đi qua $(0, 0)$.
Ví dụ
Dữ liệu vào 1
2 1 0 10 10 NNWWSSSEEN NWWSSSEENN -1 0 8 8 NEESSWWN SEENNWWS
Dữ liệu ra 1
YES -C-C-R--S-C-C---
Dữ liệu vào 2
NO