Cho trục số ~Ox~. Có ~n~ bộ gương được lắp trên trục số, mỗi bộ được biểu diễn bằng bộ ~3~ giá trị ~(h, d, c)~ với:

• ~h~ là một trong ~2~ kí tự {'L', 'R'} có nghĩa là bộ gương được đặt bên trái tọa độ ~0~ hay bên phải tọa độ ~0~.

• Nếu ~h~ = 'L', thì những chiếc gương được đặt ở các tọa độ ~-d, -2 \cdot d, -3 \cdot d, \dots, -c \cdot d~.

• Nếu ~h~ = 'R', thì những chiếc gương được đặt ở các tọa độ ~d, 2 \cdot d, 3 \cdot d, \dots, c \cdot d~.

Lưu ý rằng với cách đặt gương này, sẽ có những tọa độ có nhiều hơn ~1~ chiếc gương.

Ở thời điểm bắt đầu ~(t = 0)~, có ~1~ tia laze sẽ bắt đầu được chiếu từ trái qua phải với vận tốc không đổi là một đơn vị trên giây. Khi laze chạm vào một chiếc gương, nó sẽ phá hủy chiếc gương và chuyển hướng đối diện ngay lập tức. Nếu có nhiều chiếc gương được đặt cùng ~1~ chỗ, chỉ có ~1~ chiếc gương bị phá hủy.

Bạn được cho ~q~ truy vấn, mỗi truy vấn bạn được cho một số nguyên dương ~T~, nhiệm vụ của bạn là hãy xác định vị trí của tia laze tại giây thứ ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 250\,000)~.

• Mỗi dòng trong ~N~ dòng tiếp theo chứa ~3~ giá trị ~h, d~ và ~c~, với ~h~ thuộc {'L', 'R'} và ~(1 \le d, c \le 10^{12})~, miêu tả cách bộ gương được đặt.

• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương duy nhất ~T~ ~(0 \le T \le 10^{12})~ mô tả truy vấn.

Output

In ra ~q~ dòng tương ứng với câu trả lời của ~q~ truy vấn.

Scoring

Sample Input 1

3 10
L 3 2
R 3 2
L 6 1
10
9
8
7
6
5
4
3
2
1

Sample Output 1

-2
-3
-2
-1
0
1
2
3
2
1