W Lesie Bajtockim rośnie $10^6$ drzew ułożonych w rzędzie i ponumerowanych kolejno od 1 do $10^6$. Na skraju lasu, tuż przed drzewem numer 1, mieszka Bajtazaur.

Bajtazaur postanowił przejść na dietę i rozpocząć sportowy tryb życia. Przygotował plan na następne $n$ dni: $i$-tego dnia zrobi spacer z domu do drzewa numer $a_i$ i z powrotem, zjadając z każdego napotkanego drzewa dokładnie $v_i$ liści, ale z każdego drzewa tylko raz w trakcie jednego spaceru*.

Początkowo Bajtazaur ambitnie postanowił, że $v_i = 0$ dla każdego $i$, lecz szybko się zorientował, że raczej nie wytrzyma takiej głodówki i powinien stopniowo dostosowywać ilość podjadanych liści. Bajtazaur naprawi swój plan przy pomocy $m$ modyfikacji: $j$-ta modyfikacja będzie polegać na zwiększeniu liczby zjadanych liści o wartość $w_j$ dla pierwszych $p_j$ dni. Innymi słowy, dla każdego $i = 1, 2, \dots, p_j$, wartość $v_i$ zostanie zwiększona o $w_j$.

Co jakiś czas, pomiędzy wykonywanymi modyfikacjami, Bajtazaur będzie zadawał pytania. Sumarycznie zada $z$ pytań, $j$-te z nich będzie brzmiało: ile liści z drzewa numer $d_j$ zostanie zjedzonych przez Bajtazaura sumarycznie w trakcie pierwszych $p_j$ dni aktualnego planu?

Pomóż Bajtazaurowi i odpowiedz na jego pytania.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite $n, m$ oraz $z$ ($1 \le n, m, z \le 10^6, n \cdot m \cdot z \le 10^{16}$), oznaczające odpowiednio: liczbę dni zaplanowanej diety Bajtazaura, liczbę modyfikacji, których Bajtazaur dokona, oraz liczbę pytań, na które Bajtazaur potrzebuje odpowiedzi.

W drugim wierszu znajduje się ciąg $n$ liczb całkowitych $a_1, \dots, a_n$ ($1 \le a_i \le 10^6$), oznaczających numery drzew, do których Bajtazaur będzie spacerował w poszczególnych dniach planu.

W kolejnych $m+z$ wierszach znajdują się opisy modyfikacji planu oraz opisy pytań Bajtazaura, po jednym opisie w wierszu:

• Wiersz opisujący $j$-tą modyfikację planu składa się z trzech liczb całkowitych $1, p_j, w_j$ ($1 \le p_j \le n, 1 \le w_j \le 10^6$), oznaczających odpowiednio liczbę dni oraz wartość o jaką Bajtazaur zwiększa liczby zjadanych liści.
• Wiersz opisujący $j$-te pytanie składa się z trzech liczb całkowitych $2, p_j, d_j$ ($1 \le p_j \le n, 1 \le d_j \le 10^6$), oznaczających odpowiednio liczbę dni oraz drzewo, dla którego mamy policzyć zjedzone liści.

Pośród tych $m + z$ wierszy znajdzie się dokładnie $m$ opisów modyfikacji i dokładnie $z$ opisów pytań. Opisy są podane w kolejności chronologicznej, czyli przy odpowiedzi na dane pytanie, należy w planie uwzględnić te modyfikacje, które zostały wykonane przed zadaniem pytania (tj. są podane wcześniej na wejściu), natomiast nie należy uwzględniać modyfikacji, które będą wykonane później (tj. są podane później na wejściu).

Wyjście

Na wyjściu powinno znaleźć się $z$ wierszy, a $j$-ty z nich powinien zawierać odpowiedź na $j$-te pytanie, tzn. liczbę liści jakie Bajtazaur zje z drzewa numer $d_j$ w przeciągu pierwszych $p_j$ dni planu rozważanego przez Bajtazaura w momencie zadania pytania.

*Bajtazaur wymyślił sobie, że w jedną stronę będzie jadł tylko z drzew o nieparzystych numerach, a z powrotem będzie jadł tylko z drzew o numerach parzystych. W ten sposób rozłoży posiłki równomiernie na całej trasie.

Przykład

Przykład 1

3 2 4
3 4 1
2 3 1
1 2 10
2 1 2
2 3 1
1 3 1
2 3 2

Wyjście 1

0
10
20
22

Uwagi

Wyjaśnienie do przykładu: Plan Bajtazaura składa się z trzech dni ($n = 3$). Bajtazaur wykona $m = 2$ modyfikacji początkowego planu i zada $z = 4$ pytania.

W dniu pierwszym, plan przewiduje spacer do drzewa numer $a_1 = 3$, w dniu drugim do drzewa numer $a_2 = 4$, a w dniu trzecim do drzewa numer $a_3 = 1$. Na początku $v_1 = v_2 = v_3 = 0$, czyli Bajtazaur nie planuje jeść liści. Następnie Bajtazaur wykonuje modyfikacje i zadaje pytania:

• $2 \ 3 \ 1$ – Bajtazaur pyta, ile liści zje przez pierwsze 3 dni planu z drzewa numer 1 – odpowiedź to 0, ponieważ Bajtazaur jeszcze nie zaplanował jedzenia.
• $1 \ 2 \ 10$ – Bajtazaur modyfikuje plan poprzez zwiększenie wartości $v_i$ dla pierwszych 2 dni o 10. Po tej modyfikacji mamy: $v_1 = 10, v_2 = 10, v_3 = 0$.
• $2 \ 1 \ 2$ – Bajtazaur pyta, ile liści zje w trakcie tylko pierwszego dnia planu z drzewa numer 2 – odpowiedź to 10, ponieważ pierwszego dnia podczas spaceru do drzewa numer $a_1 = 3$, zje $v_1 = 10$ liści z drzewa numer 2, które jest po drodze.
• $2 \ 3 \ 1$ – Bajtazaur pyta, ile liści zje przez pierwsze 3 dni planu z drzewa numer 1 – tym razem odpowiedź to 20, ponieważ pierwszego dnia zje $v_1 = 10$ liści, drugiego dnia zje $v_2 = 10$ liści, a trzeciego dnia zje $v_3 = 0$ liści.
• $1 \ 3 \ 1$ – Bajtazaur modyfikuje plan poprzez zwiększenie wartości $v_i$ dla pierwszych 3 dni o 1. Po tej modyfikacji mamy: $v_1 = 11, v_2 = 11, v_3 = 1$.
• $2 \ 3 \ 2$ – Bajtazaur pyta, ile liści zje przez pierwsze 3 dni planu z drzewa numer 2 – odpowiedź to 22, ponieważ pierwszego dnia zje $v_1 = 11$ liści, drugiego dnia zje $v_2 = 11$ liści, a trzeciego dnia pójdzie na spacer tylko do drzewa $a_3 = 1$, więc drzewa 2 w ogóle nie odwiedzi.

Podzadania

W poniższej tabeli, zapis $a \sim b$ oznacza $0.99 \cdot b < a \le b$.