Pinball (RMI contest)
Time limit: 3 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: arithmetic, data structures, simulation, optimization

# Pinball

Time limit: *3000 ms*
Memory limit: *256 MB*

> — 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*len, -3*len, ..., -freq*len`
* if `dir = R`, then the walls in the set are placed at
    `len, 2*len, 3*len, ..., freq*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 1 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).

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

## Standard input

The first line of input will contain the integers N and Q, separated by one space.
The next N lines contain three space-separated values, `dir`, `len` and `freq`, describing how the walls are placed. (`dir` will be 'L' or 'R', `len` and `freq` will be integers).
The next Q lines contain an integer, T, describing a query.

## Standard output

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

## Constraints and notes

* 1 <= N, Q <= 250,000
* 1 <= T <= 10^12
* `dir` is either 'L' or 'R'
* 1 <= `len`, `freq` <= 10^12

| # | Points | Restrictions                    |
|---|--------|---------------------------------|
| 1 | 13     | N, Q <= 1000                    |
| 2 | 8      | Q, T <= 1000                    |
| 3 | 16     | 1 <= len <= 10                  |
| 4 | 10     | T <= 10^6                       |
| 5 | 11     | len * freq <= 10^6              |
| 6 | 9      | Let S be the sum of all `freq` in the input. S <= 10^6 |
| 7 | 33     | No further restrictions.        |

---

**Example:**

*Input:*
```
3 12
R 3 2
R 6 1
L 3 2
0
1
2
3
4
5
6
7
17
18
19
200
```
*Output:*
```
0
1
2
3
2
1
0
-1
5
6
5
-152
```

---

Starter code:

Grader code:

Setup script:

Evaluation script: