Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia.

Arborele binar de mai jos este complet:

Înălțimea unui arbore binare complet este \( \left[ log_2 n \right] + 1 \), unde \(n\) este numărul de noduri.

Pentru reprezentarea unui arbore binar complet se poate folosi un tablou unidimensional A cu n elemente, în felul următor:

• rădăcinii arborelui îi corespunde elementul A[1];
• dacă unui nod îi corespunde elementul A[k], descendentului stâng îi va corespunde elementul A[2*k], iar celui drept îi va corespunde elementul A[2*k+1].

Observăm că pentru un nod A[k], nodul părinte este A[k/2], unde k/2 este câtul împărțirii, fără zecimale.

Într-un arbore reprezentat astfel, nodurile de pe ultimul nivel sunt grupate în stânga. Dacă nodurile nu sunt grupate în stânga, sunt necesare câteva elemente în plus în vector, iar unele dintre ele nu vor fi folosite – nu vor avea un nod corespunzător.

Cerința

Se dau n numere naturale, reprezentând în ordine valorile nodurilor dintr-un arbore binar complet și m operații de tip 1 sau 2, aplicate unui nod k.

Operația de tip 1 determină valoarea nodului părinte a lui k, iar operația de tip 2 determină suma valorilor fiilor nodului k. Dacă k=1 sau dacă nodul k nu are fii, rezultatul va fi 0.

Afișați pentru fiecare operație rezultatul ei.

Date de intrare

Fișierul de intrare complet.in conține pe prima linie numărul n, pe linia a doua n numere naturale, pe linia a treia m, iar pe următoarele m linii câte o pereche op k.

Date de ieșire

Fișierul de ieșire complet.out va conține rezultatele celor m operații, în ordine, câte unul pe linie.

Restricții și precizări

• 1 ≤ n ≤ 100000
• cele n numere citite vor fi mai mici decât 1.000.000
• 1 ≤ m ≤ 100000
• 1 ≤ op ≤ 2
• 1 ≤ k ≤ n

Exemplu:

complet.in

12
15 5 18 35 32 23 12 43 29 25 22 13
8
2 9
1 7
2 5
1 8
1 1
2 6
1 9
2 4 

complet.out

0
18
47
35
0
13
35
72

Explicație

Exemplul corespunde arborelui de mai sus.