Người hâm mộ quá khích

Đề bài

Hôm nay sẽ là ngày ấy — hôm nay sẽ là ngày bạn cuối cùng cũng chụp được một bức ảnh với chú mèo Peppurr!

Người ta vừa thông báo rằng Peppurr sẽ đi lưu diễn quanh thành phố của bạn. Thành phố có vô hạn con đường dài vô hạn chạy theo hướng bắc–nam và vô hạn con đường dài vô hạn chạy theo hướng đông–tây. Một giao lộ là bất kỳ điểm nào mà một con đường bắc–nam gặp một con đường đông–tây. Từ một giao lộ bất kỳ, giao lộ gần nhất theo mỗi trong bốn hướng (bắc, đông, nam và tây) nằm cách đúng một khu phố.

Bạn biết chính xác lộ trình mà chuyến lưu diễn của Peppurr sẽ đi qua trên các con đường đó. Mục tiêu của bạn là có mặt tại một trong các giao lộ thuộc lộ trình của Peppurr đúng lúc Peppurr ở đó, và bạn muốn làm điều này sớm nhất có thể. Đó là cách bạn sẽ chụp được ảnh với Peppurr!

Chuyến lưu diễn của Peppurr bắt đầu tại một giao lộ nằm cách giao lộ nơi bạn đang đứng X khu phố về phía đông và Y khu phố về phía bắc. Cả bạn và Peppurr đều mất đúng một phút để đi hết một khu phố và phải kết thúc mỗi phút tại một giao lộ; không ai trong hai có thể chỉ đi một phần khu phố.

Peppurr di chuyển theo một lộ trình định trước. Trong mỗi phút, bạn có thể chọn đứng yên suốt phút đó, hoặc dùng phút đó để đi một khu phố theo một trong 4 hướng (bắc, đông, nam hoặc tây). Cả bạn và Peppurr chỉ đi dọc theo các con đường.

Nếu bạn và Peppurr ở cùng một giao lộ vào cùng một thời điểm, bạn có thể chụp ảnh, kể cả tại giao lộ cuối cùng của chuyến lưu diễn. Tuy nhiên, Peppurr không thể chụp ảnh sau khi chuyến lưu diễn kết thúc, vì vậy nếu bạn đến giao lộ cuối cùng chỉ muộn hơn thời điểm kết thúc dù một phút thì bạn cũng sẽ không chụp được ảnh.

Liệu bạn có thể chụp ảnh với Peppurr không? Nếu có, bạn có thể làm được sớm nhất sau bao lâu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test T. Tiếp theo là T bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên X, Y và một chuỗi ký tự M. Điều này biểu thị rằng chuyến lưu diễn của Peppurr bắt đầu cách bạn đúng X khu phố về phía đông và Y khu phố về phía bắc. Chuỗi M là dãy các bước di chuyển mà Peppurr sẽ thực hiện. Ký tự thứ \(i\) trong M là một trong N, E, S hoặc W, tương ứng với hướng (lần lượt là bắc, đông, nam hoặc tây) mà Peppurr sẽ đi một khu phố trong phút thứ \(i\) của chuyến lưu diễn.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ 1). Nếu không có cách nào chụp ảnh với Peppurr, y là IMPOSSIBLE. Nếu không, y là số phút nhỏ nhất tính từ lúc chuyến lưu diễn bắt đầu cần để chụp được ảnh với Peppurr.

Ràng buộc

• \(1 \le T \le 100\).
• \((X, Y) \ne (0, 0)\). (Chuyến lưu diễn không bắt đầu tại cùng giao lộ với bạn.)

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(0 \le X \le 10\).
• \(0 \le Y \le 10\).
• \(1 \le\) độ dài của M \(\le 8\).
• Mỗi ký tự trong M là một chữ cái in hoa — N hoặc S.

Test Set 2 (Phán quyết hiển thị)

• \(0 \le X \le 1000\).
• \(0 \le Y \le 1000\).
• \(1 \le\) độ dài của M \(\le 1000\).
• Mỗi ký tự trong M là một chữ cái in hoa — N hoặc S.

Test Set 3 (Phán quyết hiển thị)

• \(0 \le X \le 1000\).
• \(0 \le Y \le 1000\).
• \(1 \le\) độ dài của M \(\le 1000\).
• Mỗi ký tự trong M là một chữ cái in hoa — N, E, S hoặc W.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
4 4 SSSS
3 0 SNSS
2 10 NSNNSN
0 1 S
2 7 SSSSSSSS

Case #1: 4
Case #2: IMPOSSIBLE
Case #3: IMPOSSIBLE
Case #4: 1
Case #5: 5

2
3 2 SSSW
4 0 NESW

Case #1: 4
Case #2: 4

Nguồn

Google Code Jam 2020, Vòng 1C, bài Overexcited Fan.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.