— Calm yourselves a little...

We have a ball which lies on the $X$ axis, initially placed at the $0$ coordinate. We also have $N$ sets of walls which lie on the $X$ axis. Each set is described as a tuple $(dir,len,freq)$ where:

• $dir$ indicates the direction in which the walls are placed, which can either be L (left) or R (right)
• if $dir=$ L, then the walls in the set are placed at $−len$, $−2 \cdot len$, $−3 \cdot len$, ..., $−freq \cdot len$
• if $dir=$ R, then the walls in the set are placed at $len$, $2 \cdot len$, $3 \cdot len$, ..., $freq \cdot len$

Note that through the nature of these informations, there can be multiple walls placed at the same coordinate.

At time $T=0$ the ball starts moving to the right with a constant speed of one unit per second. When the ball hits a wall, the wall is automatically destroyed and the ball reverses its direction. If there are multiple walls situated at the same coordinate, only one of the walls is destroyed.

Task

You are given $Q$ queries. For each query you are given an integer $T$. Output the coordinate of the ball after $T$ seconds.

Input data

The first line of input will contain the integers $N$ and $Q$, separated by one space.

The next $N$ lines contain three space-separated integers, $dir$, $len$ and $freq$, describing how the walls are placed.

The next $Q$ lines contain an integer, $T$, describing a query.

Output data

Output $Q$ lines, the $i$−th line should contain the answer for $i$−th query.

Constraints and clarifications

• $1 \leq N, Q \leq 250 \ 000$
• $1 \leq T \leq 10^{12}$
• $dir \in \{$L$,$ R$\}$
• $1 \leq len, freq \leq 10^{12}$

Example

stdin

3 12
R 3 2
R 6 1
L 3 2
0
1
2
3
4
5
6
7
17
18
19
200

stdout

0
1
2
3
2
1
0
-1
5
6
5
-152