Záhradník Adam sa jedného dňa zobudil a zistil, že zdedil obrovské pole. Pole to nebolo len také, bolo to pole iné, bolo to pole veľké, priam rozsiahle a na Adamove prekvapenie nebolo uložené v počítači, ale jednalo sa o poriadne pole, s traktormi, hnojiskami a zavlažovačmi.

Tak sa Adam rozhodol že bude teda poriadne záhradníčiť.

Prvý krok je inšpekcia pôdy.

Na poli je $n$ zavlažovačov, ktoré sú vskutku atypické – každý zavlažovač je natočený do jedného zo štyroch smerov (doprava dole, doprava hore, doľava dole alebo doľava hore) a rovnomerne zavlažuje všetku plochu v rohu na ktorý je natočený. Rôzne zavlažovače zavlažujú s rôznou intenzitou. Zavlažovače sú fixne zabudované v poli a Adam s nimi nevie hýbať.

Adam má $m$ miest na poli, kde by chcel začať pestovať. Avšak najskôr by potreboval vedieť, ako veľmi zavlažované jednotlivé miesta sú. Pomôžte mu!

Úloha

Na poli je $n\leq 100\,000$ zavlažovačov, a $m\leq 20\,000$ miest ktoré Adama zaujímajú.

Každý zavlažovač má danú pozíciu na poli, smer a intenzitu. Zavlažovač zavlažuje tú čast poľa na ktorú je nasmerovaný. Ak je napríklad zavlažovač na pozícii (0,0) a je nastavený doprava-hore, zavlažuje všetky políčka s nezápornými súradnicami.

Vlaha na pozícii je súčet intenzít všetkých zavlažovačov zavlažujúcich túto časť poľa.

Pre všetky miesta, ktoré Adama zaujímajú zistite, aká je ich vlaha.

Navyše, v niektorých sadách by chcel Adam vedieť odpovede ihneď - predtým ako sa spýta ďalšiu otázku. Na získanie plného počtu bodov musí váš program vedieť odpovedať online.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo $n$ ($1 \leq n \leq 100\,000$).

Na ďalších $n$ riadkoch sú medzerou oddelené čísla $x_i$, $y_i$ – pozície $i$-teho zavlažovača, $v_i$ – intenzita $i$-teho zavlažovača a ukazovateľ smeru. “DP” znamená dole-pravo, $DL$ je dole-ľavo, $HL$ je hore-ľavo a $HP$ je hore-pravo.

Nasledujú dve medzerou oddelené celé čísla $m$ ($1\leq m\leq 20\,000$) – počet miest, ktoré zaujímajú Adama, a $k$ ($0\leq k\leq 1$).

Nasleduje $m$ riadkov, na každom z nich sú dve medzerou oddelené čísla, $x$ $y$. Ak $k = 0$, potom pozície miesta sú $x$ $y$.

Ak $k = 1$, nech $a$ je vlhkosť predchádzajúceho miesta. Potom súradnice sú $x \oplus a$ $y\oplus a$, kde $\oplus$ je bitový xor.

Pozície miest a zavlažovačov sa môžu zhodovať. Dva zavlažovače sa môžu nachádzať na rovnakom mieste.

Všetky súradnice v absolútnej hodnote nepresahujú $10^9$. Všetky intenzity sú celé čísla v rozsahu $1$ až $10^4$.

Formát výstupu

Vypíšte $m$ riadkov, na každom z nich vlahu na $i$-tom mieste, v poradí v akom boli zadané na vstupe.

Hodnotenie

Existuje $8$ testovacích sád, každá za jeden bod.

V prvých dvoch sadách sú všetky súradnice medzi $0$ a $1000$.

V prvej a tretej sade platí, že $m, n \leq 1000$.

V štvrtej a piatej sade navyše platí, že všetky súradnice sú medzi $0$ a $10^5$.

Vo všetkých sadách okrem siedmej a ôsmej platí $k = 0$.

Príklady

Input:

5
-1 -1 1 DL
-1 1 2 HL
1 -1 4 DP
1 1 8 HP
0 1 3 DP
7 0
-100 100
0 1
2 1
-1 0
0 -5
2 -2
-1000000000 -1000000000

Output:

2
3
11
0
3
7
1

Input:

5
-1 -1 1 DL
-1 1 2 HL
1 -1 4 DP
1 1 8 HP
0 1 3 DP
2 1
-100 100
2 3

Output:

2
3

*Pozície zavlažovačov a miest sú rovnaké ako v prvom vstupe. Lenže v tomto prípade je $k = 1$.