Đi Bộ Manhattan

• $Q$ con bò của bác John đã trốn thoát ở Manhattan và đi bộ theo các quy tắc nhất định. Manhattan có $N$ con đường chạy theo phương ngang hoặc dọc, mô tả bằng $y=c_i$ hoặc $x=c_i$.

Quy tắc di chuyển:

• Bò di chuyển về phía bắc (+y) hoặc phía đông (+x) với tốc độ 1 đơn vị/giây.
• Trên một con đường đơn lẻ: bò tiếp tục theo hướng của con đường đó (ngang = đông, dọc = bắc).
• Tại ngã tư (giao của đường ngang và dọc): đi về phía bắc nếu số giây đã đi là chẵn, đi về phía đông nếu lẻ.
• Không trên đường nào: dùng quy tắc chẵn/lẻ như tại ngã tư.

Cho vị trí ban đầu và thời gian đã đi của mỗi con bò, hãy tìm vị trí hiện tại của chúng.

Dữ liệu vào

• Dòng đầu tiên: hai số nguyên $N$ và $Q$ ($1\le N,Q\le 2\times {10}^5$).
• $N$ dòng tiếp theo: ký tự $d$ (H hoặc V) và số nguyên $c_i$ ($0\le c_i\le {10}^9$) - mô tả đường.
• $Q$ dòng tiếp theo: ba số nguyên $x_i$, $y_i$, $d_i$ ($0\le x_i,y_i,d_i\le {10}^9$) - vị trí bắt đầu và số giây đã đi.

Dữ liệu ra

• $Q$ dòng, mỗi dòng chứa hai số nguyên - vị trí hiện tại $(x,y)$ của mỗi con bò.

Ràng buộc

• $1\le N,Q\le 2\times {10}^5$
• $0\le c_i,x_i,y_i,d_i\le {10}^9$

Ví dụ