8. Areál zavlažovačov

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\).