Nông trại của nông dân John có tất cả \(N\) (\(2 \leq N \leq 2 \times 10^5\)) con bò, được đánh số từ \(1\) đến \(N\). Những con bò đang đứng hóng gió ở vị trí có tọa độ (\(x_i, y_i\)) trên bản đồ của trang trại mô tả dưới dạng trục hai chiều.

Do những con bò quá lười, nông dân John muốn tổ chức một trò chơi cho chúng. Anh John chia đàn bò thành đội "xanh" và "đỏ" theo những quy tắc sau:

• Không có đội nào không có thành viên.
• Mỗi một con bò thuộc tối đa một đội (có thể là không đội nào).
• Một tấm lưới có độ dài vô tận sẽ được đặt song song với trục tung hoặc trục hoành trên bản đồ trang trại, trên một vị trí không nguyên (ví dụ như \(x = 0.5\)).

Nhiệm vụ của bạn là giúp nông dân John chia đàn bò thành hai đội và đặt lưới ở giữa hai đội, biết đàn bò quá lười để di chuyển khỏi vị trí chúng đang ở. Hãy nói cho John biết có tất cả bao nhiêu cách để chọn hai đội sao cho thỏa mãn những điều kiện trên, tính theo modulo \(10^9 +7\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).
• \(N\) dòng tiếp theo gồm một kí tự H(orizontal) hoặc V(ertical) và một số nguyên mô tả hướng của con đường và vị trí bắt đầu của nó. Dữ liệu đảm bảo những con đường đều phân biệt.
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x_i, y_i, z_i\) \((0 \leq x_i, y_i, z_i \leq 10^9)\), đại diện cho vị trí bắt đầu và thời gian tính từ lúc ghi nhận vị trí đến hiện tại. Dữ liệu đảm bảo những con bò luôn xuất phát trên một con đường bất kì.

Output

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

Scoring

• Subtask 1: \(N, Q, c_i,x_i,y_i,d_i \leq 100\).
• Subtask 2: \(N,Q \leq 3000\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

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