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