— 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}$

# | Points | Constraints |
---|---|---|

0 | 0 | Examples |

1 | 13 | $N, Q \leq 1 \ 000$ |

2 | 8 | $Q, T \leq 1 \ 000$ |

3 | 16 | $1 \leq len \leq 10$ |

4 | 10 | $T \leq 10^6$ |

5 | 11 | $len \cdot freq \leq 10^6$ |

6 | 9 | Let $S$ be the sum of all $freq$ in the input. $S \leq 10^6$ |

7 | 33 | No additional constraints |

## 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
```