Дана последовательность $A_0, A_1, \ldots, A_{N-1}$ длины $N$. Напишите программу, которая обрабатывает следующие запросы ($0 \le A_i < 2^{32}$):

• 1 p v: Вставить $v$ перед $A_p$. Если $p$ равно длине $A$, вставка производится в конец. ($0 \le p \le$ длина $A$, $0 \le v < 2^{32}$)
• 2 p: Удалить $A_p$. ($0 \le p <$ длина $A$)
• 3 p v: Заменить $A_p$ на $v$. ($0 \le p <$ длина $A$, $0 \le v < 2^{32}$)
• 4 l r k: Вычислить $(\sum A_i \times (i - l + 1)^k) \bmod 2^{32}$ и вывести результат. ($0 \le k \le 10$)

Входные данные

Первая строка содержит длину последовательности $N$ ($1 \le N \le 100{,}000$).

Вторая строка содержит $A_0, A_1, \ldots, A_{N-1}$.

Третья строка содержит количество запросов $M$ ($1 \le M \le 100{,}000$).

Следующие $M$ строк содержат по одному запросу.

Выходные данные

Для каждого запроса выведите ответ в отдельной строке.

Примеры

Входные данные 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

Выходные данные 1

6
26
40
4