Có rất nhiều hàng quán đường phố tuyệt vời ở Manhattan, nhưng chắc chắn nơi có đồ ăn ngon nhất chính là xe bánh crepe Code Jam!

Bạn muốn tìm chiếc xe, nhưng ngoài việc biết nó nằm tại một giao lộ nào đó, bạn không biết chính xác nó ở đâu. Bạn tin rằng mọi người từ khắp Manhattan hiện đang đi về phía giao lộ ấy, vì vậy bạn sẽ cố xác định giao lộ mà nhiều người đang đi về phía đó nhất.

Trong phạm vi bài toán này, Manhattan là một lưới đều có các trục thẳng theo hướng la bàn và mỗi trục được giới hạn từ \(0\) đến \(Q\), kể cả hai đầu. Các đường phố theo hướng tây–đông tương ứng với các đường lưới \(y = 0, y = 1, y = 2, \ldots, y = Q\); các đường phố theo hướng nam–bắc tương ứng với các đường lưới \(x = 0, x = 1, x = 2, \ldots, x = Q\); và mọi người chỉ di chuyển dọc theo những con phố này. Những điểm mà các đường gặp nhau — chẳng hạn \((0, 0)\) và \((1, 2)\) — là các giao lộ. Khoảng cách ngắn nhất giữa hai giao lộ được đo bằng khoảng cách Manhattan, tức là tổng độ chênh lệch tuyệt đối theo phương ngang và phương dọc giữa hai cặp tọa độ.

Bạn biết vị trí của \(P\) người, tất cả đều đang đứng tại các giao lộ, cùng hướng la bàn mà mỗi người đang đi: bắc (tung độ \(y\) tăng), nam (tung độ \(y\) giảm), đông (hoành độ \(x\) tăng), hoặc tây (hoành độ \(x\) giảm). Một người được xem là đang đi về phía một giao lộ nếu hướng di chuyển hiện tại của họ nằm trên một đường đi ngắn nhất đến giao lộ đó trong lưới Manhattan. Chẳng hạn, nếu một người ở \((x_0, y_0)\) đang đi về phía bắc, thì họ đang đi về phía tất cả các giao lộ \((x, y)\) thỏa mãn \(y > y_0\).

Bạn cho rằng xe bánh crepe nằm tại giao lộ mà nhiều người đang đi về phía đó nhất. Hơn nữa, bạn tin rằng xe bánh crepe có nhiều khả năng xuất hiện ở phần phía nam và phía tây của đảo hơn. Vì thế, nếu có nhiều giao lộ như vậy, bạn sẽ chọn giao lộ có hoành độ \(x\) không âm nhỏ nhất; nếu vẫn có nhiều giao lộ có cùng hoành độ đó, bạn chọn giao lộ có tung độ \(y\) không âm nhỏ nhất trong số chúng. Bạn sẽ chọn giao lộ nào?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(P\) và \(Q\): số người và giá trị lớn nhất có thể có của một hoành độ hoặc tung độ tại Manhattan như mô tả ở trên. Sau đó có thêm \(P\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(X_i\) và \(Y_i\), là vị trí hiện tại (góc phố) của một người, và một ký tự \(D_i\), là hướng người đó đang đi. \(D_i\) là một trong các chữ cái in hoa N, S, E hoặc W, lần lượt biểu thị hướng bắc, nam, đông và tây.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #t: x y, trong đó t là số thứ tự bộ test (bắt đầu từ \(1\)), còn x và y lần lượt là hoành độ và tung độ của giao lộ mà bạn cho rằng xe bánh crepe đang ở đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le P \le 500\).
• \(0 \le X_i \le Q\) với mọi \(i\).
• \(0 \le Y_i \le Q\) với mọi \(i\).
• Với mọi \(i\), nếu \(X_i = 0\) thì \(D_i \ne\) W.
• Với mọi \(i\), nếu \(Y_i = 0\) thì \(D_i \ne\) S.
• Với mọi \(i\), nếu \(X_i = Q\) thì \(D_i \ne\) E.
• Với mọi \(i\), nếu \(Y_i = Q\) thì \(D_i \ne\) N.

Phân nhóm

Test Set 1 (Công khai)

\(Q = 10\).

Test Set 2 (Ẩn)

\(Q = 10^5\).

Đ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ụ

3
1 10
5 5 N
4 10
2 4 N
2 6 S
1 5 E
3 5 W
8 10
0 2 S
0 3 N
0 3 N
0 4 N
0 5 S
0 5 S
0 8 S
1 5 W

Case #1: 0 6
Case #2: 2 5
Case #3: 0 4

Nguồn

Google Code Jam 2019, Vòng 1B, bài Manhattan Crepe Cart.

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