Taulukossa on n lukua, ja ne on indeksoitu 1,2,\ldots,n. Tehtäväsi on toteuttaa tietorakenne, joka tarjoaa seuraavat operaatiot:

1. lisää välille [a,b] lukujono x+ky (ensimmäiseen lukuun x, toiseen lukuun x+y, kolmanteen lukuun x+2y jne.)
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 y". Tämä tarkoittaa, että välin [a,b] lukuja tulee kasvattaa parametreilla x ja y.

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
• -100 \le x, y \le 100

Esimerkki

Syöte:

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

Tuloste:

17
42