길이가 $N$인 수열 $A_0, A_1, \ldots, A_{N-1}$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. ($0 \le A_i < 2^{32}$)

• 1 p v: $A_p$의 앞에 $v$를 추가한다. $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: $l \le i \le r$에 대해서 $(\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$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

출력

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

Sample

Input

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

Output

6
26
40
4