Pinball - Problem

# 10143. Pinball

Statistics

— 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

stdout

— Liniștiți-vă puțin...

Avem o bilă ce se află pe axa $X$ , inițial plasată la coordonata $0$ . Mai există și $N$ mulțimi de ziduri ce se află pe axa $X$ . Fiecare mulțime este descrisă ca un triplet $(dir, len, freq)$ , unde:

$dir$ indică direcția în care zidurile sunt plasate, aceasta putând fi fie L (stânga) sau R (dreapta)
dacă $dir=$ L, atunci zidurile din mulțime sunt puse la pozițiile $−len$ , $−2 \cdot len$ , $−3 \cdot len$ , ..., $−freq \cdot len$
dacă $dir=$ R, atunci zidurile din mulțime sunt puse la pozițiile $len$ , $2 \cdot len$ , $3 \cdot len$ , ..., $freq \cdot len$

De observat că prin natura acestor informații, pot fi multiple ziduri plasate la aceeași coordonată.

La timpul $T=0$ bila începe să se miște la dreapta cu o viteză constantă de o unitate pe secundă. Când bila se lovește de un zid, zidul este automat distrus și bila își schimbă direcția. Dacă se află mai multe ziduri la aceeași coordonată, doar unul dintre ele va fi distrus.

Cerință

Se dau $Q$ întrebări. La fiecare întrebare se va da un număr întreg $T$ . Afișați coordonata bilei după $T$ secunde.

Date de intrare

Prima linie a intrării va conține numerele întregi $N$ și $Q$ , separate de un spațiu.

Următoarele $N$ linii conțin câte trei numere întregi separate prin spații, $dir$ , $len$ și $freq$ , descriind cum sunt plasați pereții.

Următoarele $Q$ linii conțin un număr întreg, $T$ , descriind o întrebare.

Date de ieșire

Afișați $Q$ linii, a $i$ −a linie conținând răspunsul pentru cea de a $i$ −a întrebare.

Restricții

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

#	Punctaj	Restricții
0	0	Exemplele
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	Fie $S$ suma tuturor $freq$ din input. $S \leq 10^6$
7	33	Fără restricții suplimentare

Exemplu