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

Exemplu

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