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

1. kasvata jokaista välillä [a,b] olevaa lukua x:llä
2. laske välin [a,b] lukujen summa

Syöte

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

Seuraavalla rivillä on n lukua t_1,t_2,\ldots,t_n, jotka kuvaavat taulukon alkusisällön.

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

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

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

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

Tuloste

Tulosta jokaisesta tyypin 2 kyselystä lukujen summa omalle rivilleen.

Rajat

• 1 \le n \le 10^5
• -10^6 \le t_i \le 10^6
• 1 \le q \le 10^5
• 1 \le a \le b \le n
• -10^6 \le x \le 10^6

Esimerkki 1

Syöte:

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

Tuloste:

7
11
21

Esimerkki 2

Syöte:

10
-10 3 -1 4 4 1 6 7 9 3
20
1 7 10 -5
1 5 9 2
2 1 5
1 8 10 -8
1 1 7 5
1 8 9 1
1 2 5 6
2 4 7
2 5 10
1 2 5 -1
2 1 9
1 2 8 9
1 7 8 1
1 5 10 4
1 6 7 -4
1 5 8 3
1 5 9 -2
1 2 6 6
2 5 6
1 6 8 -9

Tuloste:

2
48
19
59
60