Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $N$ ($1 \le N \le 200\,000$), oznaczającą długość ciągu.

Drugi wiersz zawiera $N$ liczb $A_1, A_2, \ldots, A_N$ ($-10^6 \le A_i \le 10^6$).

Trzeci wiersz zawiera liczbę zapytań $M$ ($1 \le M \le 200\,000$).

Następnie w $M$ wierszach podane są kolejne zapytania, każde w osobnym wierszu. ($1 \le L \le R \le N$, $1 \le S \le E \le N$, $E-S = R-L$, $-10^6 \le X \le 10^6$) Zapytania typu 3 pojawiają się co najmniej raz.

Wyjście

Dla każdego zapytania typu 3 wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście 1

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

Wyjście 1

15
9
20