Farmer John và \(Q\) (\(1 \leq Q \leq 2\cdot 10^5\)) con bò của ông đang đi nghỉ ở Manhattan, nhưng đàn bò đã trốn thoát và giờ tự do đi lại trong thành phố! Manhattan rất lớn — lớn đến mức \(N\) (\(1 \le N \le 2\cdot 10^5\)) con đường của nó kéo dài vô hạn trên mặt phẳng \(x\)-\(y\); thật tiện lợi, tất cả các đường đều hoàn toàn nằm ngang hoặc thẳng đứng. Mỗi đường ngang hoặc dọc có thể được mô hình hóa bởi phương trình dạng \(y=c_i\) hoặc \(x=c_i\), trong đó \(c_i\) là số nguyên từ \(0\) đến \(10^9\).

Farmer John biết chính xác mỗi con bò bắt đầu đi từ đâu và chúng đã trốn thoát bao lâu. Các con bò rất dễ đoán, nên mỗi con đi theo quy luật sau:

• Chúng chỉ đi về phía bắc (\(+y\)) hoặc phía đông (\(+x\)) với tốc độ một đơn vị mỗi giây.
• Nếu đang ở trên đúng một con đường, chúng tiếp tục đi theo hướng của con đường đó.
• Nếu đang ở giao điểm của hai con đường, chúng đi về phía bắc nếu đã đi được một số giây chẵn, và đi về phía đông nếu không.

Cho bố cục Manhattan và thông tin của từng con bò, hãy giúp Farmer John xác định vị trí hiện tại của chúng!

Dữ liệu vào

Dòng đầu chứa \(N\) và \(Q\).

\(N\) dòng tiếp theo mô tả các con đường. Mỗi đường được mô tả bởi một hướng (H hoặc V) và một tọa độ \(c_i\). Đảm bảo các con đường đôi một khác nhau.

\(Q\) dòng tiếp theo mô tả các con bò. Mỗi con được mô tả bởi ba số nguyên \((x_i,y_i,d_i)\), nghĩa là nó bắt đầu đi từ \((x_i,y_i)\) đúng \(d_i\) giây trước. Đảm bảo \((x_i,y_i)\) nằm trên một con đường nào đó và \(0 \le x_i,y_i,d_i \le 10^9\).

Dữ liệu ra

In \(Q\) dòng, trong đó dòng thứ \(i\) chứa vị trí hiện tại của con bò thứ \(i\).

Ví dụ

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

14 5
7 13
6 15
6 16
110 4

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Phân nhóm

• Các test 2-4 thỏa mãn \(N,Q,c_i,x_i,y_i,d_i \leq 100\).
• Các test 5-9 thỏa mãn \(N,Q\le 3000\).
• Các test 10-20 không có ràng buộc bổ sung.

Nguồn

USACO 2024 January Contest, Gold — Walking in Manhattan: https://usaco.org/index.php?page=viewproblem2&cpid=1377

Tác giả đề: Benjamin Qi