Tehtäväsi on toteuttaa tietorakenne, joka pitää yllä listaa, jonka jokainen alkio on taulukko. Aluksi listassa on vain yksi taulukko.

Rakenteen tulee tarjota seuraavat operaatiot:

1. muuta taulukon x alkion k arvoksi u
2. laske taulukon x välin [a,b] lukujen summa
3. tee kopio taulukosta x ja lisää se listan loppuun

Taulukoissa on n lukua, ja ne on indeksoitu 1,2,\ldots,n. Listassa olevat taulukot on indeksoitu 1,2,\ldots

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 x k u". Tämä tarkoittaa, että taulukon x alkion k arvoksi tulee u.

Jos kysely on tyyppiä 2, rivi on muotoa "2 x a b". Tämä tarkoittaa, että täytyy laskea välin [a,b] summa taulukossa x.

Jos kysely on tyyppiä 3, rivi on muotoa "3 x". Tämä tarkoittaa, että taulukosta x tehdään kopio listan loppuun.

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 k \le n
• -10^6 \le u \le 10^6
• 1 \le a \le b \le n

Esimerkki

Syöte:

5
2 3 1 2 5
6
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

Tuloste:

13
13
13
15