Dany jest ciąg $A_0, A_1, \ldots, A_{N-1}$ długości $N$. Napisz program, który przetwarza następujące zapytania ($0 \le A_i < 2^{32}$):

• 1 p v: Wstaw $v$ przed $A_p$. Jeśli $p$ jest równe długości $A$, wstawiane jest na końcu. ($0 \le p \le$ długość $A$, $0 \le v < 2^{32}$)
• 2 p: Usuń $A_p$. ($0 \le p <$ długość $A$)
• 3 p v: Zamień $A_p$ na $v$. ($0 \le p <$ długość $A$, $0 \le v < 2^{32}$)
• 4 l r k: Oblicz $(\sum A_i \times (i - l + 1)^k) \bmod 2^{32}$ i wypisz wynik. ($0 \le k \le 10$)

Wejście

Pierwszy wiersz zawiera długość ciągu $N$ ($1 \le N \le 100\,000$).

Drugi wiersz zawiera $A_0, A_1, \ldots, A_{N-1}$.

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

Kolejne $M$ wierszy zawiera po jednym zapytaniu.

Wyjście

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

Przykład

Wejście 1

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

Wyjście 1

6
26
40
4