CSES - Junaetsivä
  • Time limit: 4.00 s
  • Memory limit: 128 MB

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 nn, junan vaunujen määrä. Vaunut on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Seuraavalla rivillä on nn kokonaislukua v1,v2,,vnv_1,v_2,\ldots,v_n: montako matkustajaa kussakin vaunussa on aluksi.

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

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

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

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 aa ja bb. Tällöin pitää laskea matkustajien määrä vaunujen a,a+1,,ba,a+1,\ldots,b alueella.

Tuloste

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

Rajat

  • 2n1052 \le n \le 10^5
  • 0vk1090 \le v_k \le 10^9
  • 1q1051 \le q \le 10^5
  • 1xn11 \le x \le n - 1
  • d0d \neq 0
  • aba \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