CSES - Summat
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Taulukossa on nn lukua, jotka on indeksoitu 1,2,,n1,2,\ldots,n. Toteuta tietorakenne, joka tarjoaa seuraavat operaatiot:

  1. kasvata jokaista välillä [a,b][a,b] olevaa lukua xx:llä
  2. muuta jokainen välillä [a,b][a,b] oleva luku xx:ksi
  3. laske välin [a,b][a,b] lukujen summa

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn, taulukon koko.

Seuraavalla rivillä on nn lukua t1,t2,,tnt_1,t_2,\ldots,t_n, jotka kuvaavat taulukon alkusisällön.

Sitten syötteessä on luku qq, kyselyjen määrä.

Lopuksi syötteessä on qq riviä, joista jokainen kuvaa yhden kyselyn.

Jos kysely on tyyppiä 1, rivi on muotoa "1 aa bb xx". Tämä tarkoittaa, että välin [a,b][a,b] lukuja tulee kasvattaa xx:llä.

Jos kysely on tyyppiä 2, rivi on muotoa "2 aa bb xx". Tämä tarkoittaa, että välin [a,b][a,b] luvuiksi tulee muuttaa xx.

Jos kysely on tyyppiä 3, rivi on muotoa "3 aa bb". Tämä tarkoittaa, että tulee laskea välin [a,b][a,b] lukujen summa.

Tuloste

Tulosta jokaisesta tyypin 3 kyselystä lukujen summa omalle rivilleen.

Rajat

  • 1n1051 \le n \le 10^5
  • 106ti106-10^6 \le t_i \le 10^6
  • 1q1051 \le q \le 10^5
  • 1abn1 \le a \le b \le n
  • 106x106-10^6 \le x \le 10^6

Esimerkki

Syöte:

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

Tuloste:

7
11
15