Uolevin junamatka isotädin luo piti olla rauhallinen, mutta Syrjälän seisakkeen jälkeen kreivitär huomasi, että hänen kaulakorunsa oli kähvelletty. Uolevi, vanha junaetsivä, nimitettiin johtamaan tutkimuksia. Luonnollisesti kukaan ei saisi poistua junasta ennen mysteerin ratkeamista.

Tehtäväsi on auttaa Uolevia pitämään kirjaa junan matkustajista. Saat aluksi tietää, montako matkustajaa kussakin vaunussa on. Tämän jälkeen sinun täytyy käsitellä kahdenlaisia tapahtumia: (1) joukko matkustajia siirtyy vaunusta toiseen, (2) halutaan laskea matkustajat tietyissä vaunuissa.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n, junan vaunujen määrä. Vaunut on numeroitu kokonaisluvuin 1,2,\ldots,n.

Seuraavalla rivillä on n kokonaislukua v_1,v_2,\ldots,v_n: montako matkustajaa kussakin vaunussa on aluksi.

Sitten syötteessä on kokonaisluku q: kyselyjen määrä.

Lopuksi syötteessä on q riviä, jotka kuvaavat kyselyt. Rivin ensimmäinen arvo on 1 tai 2 kyselyn tyypin mukaan.

Jos tyyppi on 1, rivillä on vielä luvut x ja d. Jos d on positiivinen, vaunusta x siirtyy d matkustajaa vaunuun x+1. Jos taas d on negatiivinen, vaunusta x+1 siirtyy -d matkustajaa vaunuun x.

Voit luottaa siihen, että vaunusta ei lähde koskaan enempää matkustajia kuin mitä siinä on sillä hetkellä.

Jos tyyppi on 2, rivillä on vielä luvut a ja b. Tällöin pitää laskea matkustajien määrä vaunujen a,a+1,\ldots,b alueella.

Tuloste

Ohjelmasi tulee tulostaa jokaiseen kyselyyn 2 matkustajien määrä alueella.

Rajat

• 2 \le n \le 10^5
• 0 \le v_k \le 10^9
• 1 \le q \le 10^5
• 1 \le x \le n - 1
• d \neq 0
• a \le b

Esimerkki

Syöte:

5
3 2 4 2 1
4
2 3 5
1 4 2
1 2 -3
2 1 2

Tuloste:

7
8