Đi Bộ Manhattan

Có $Q$ con bò trốn thoát và đang đi bộ trong thành phố Manhattan. Thành phố có $N$ con đường, mỗi con đường là một đường thẳng vô hạn: đường ngang được mô tả bởi $y=c_i$, đường dọc được mô tả bởi $x=c_i$. Các con đường đôi một khác nhau.

Mỗi con bò đi với tốc độ $1$ đơn vị mỗi giây và chỉ đi về phía bắc (chiều $+y$) hoặc phía đông (chiều $+x$). Tại mỗi thời điểm, nếu con bò đã đi được $t$ giây thì hướng đi tiếp theo của nó được xác định như sau:

• Nếu nó chỉ đang ở trên một đường ngang, nó đi về phía đông.
• Nếu nó chỉ đang ở trên một đường dọc, nó đi về phía bắc.
• Nếu nó đang ở ngã tư (điểm nằm trên cả một đường ngang lẫn một đường dọc), nó đi về phía bắc nếu $t$ chẵn và đi về phía đông nếu $t$ lẻ.

Lưu ý rằng khi đi qua một ngã tư, con bò không nhất thiết phải rẽ: nó chỉ rẽ khi quy tắc chẵn lẻ ở trên cho hướng khác với hướng nó đang đi.

Mỗi con bò xuất phát từ một điểm nằm trên ít nhất một con đường. Cho vị trí xuất phát và số giây $d_i$ mà con bò đã đi, hãy xác định vị trí của nó tại thời điểm đó.

Dữ liệu vào

• Dòng đầu tiên: hai số nguyên $N$ và $Q$.
• $N$ dòng tiếp theo: một ký tự $d$ (H cho đường ngang, V cho đường dọc) và một số nguyên $c_i$, mô tả một con đường.
• $Q$ dòng tiếp theo: ba số nguyên $x_i$, $y_i$, $d_i$, là vị trí xuất phát và số giây đã đi của con bò thứ $i$.

Dữ liệu ra

• $Q$ dòng, dòng thứ $i$ chứa hai số nguyên là hoành độ và tung độ của con bò thứ $i$ sau $d_i$ giây.

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$
• Các con đường đôi một khác nhau.
• Điểm $(x_i,y_i)$ nằm trên ít nhất một con đường.

Ví dụ