수열과 가중 합 쿼리

길이가 $N$인 수열 $A_0, A_1, \dots, A_{N-1}$이 주어진다. 모든 원소는 $0 \le A_i < 2^{32}$를 만족한다. 아래 네 가지 쿼리를 주어진 순서대로 처리하는 프로그램을 작성하시오.

• 1 p v: $A_p$의 앞에 $v$를 삽입한다. $p$가 수열의 길이와 같으면 맨 뒤에 붙인다. ($0 \le p \le$ 수열의 길이, $0 \le v < 2^{32}$)
• 2 p: $A_p$를 제거한다. ($0 \le p <$ 수열의 길이)
• 3 p v: $A_p$를 $v$로 바꾼다. ($0 \le p <$ 수열의 길이, $0 \le v < 2^{32}$)
• 4 l r k: $\left( \sum_{i=l}^{r} A_i \times (i - l + 1)^k \right) \bmod 2^{32}$을 출력한다. ($0 \le l \le r <$ 수열의 길이, $0 \le k \le 10$)

삽입이나 삭제가 일어나면 그 뒤에 있던 원소의 번호가 한 칸씩 밀리거나 당겨진다. 쿼리에 주어지는 $p$, $l$, $r$은 그 쿼리를 처리하는 시점의 수열을 기준으로 한다.

4번 쿼리의 가중치 $(i - l + 1)^k$는 구간의 왼쪽 끝을 1로 세는 상대 위치를 $k$제곱한 값이다.

첫째 줄에 수열의 크기 $N$ ($1 \le N \le 100000$)이 주어진다.

둘째 줄에 $A_0, A_1, \dots, A_{N-1}$이 공백으로 구분되어 주어진다.

셋째 줄에 쿼리의 개수 $M$ ($1 \le M \le 100000$)이 주어진다.

넷째 줄부터 $M$개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

4번 쿼리마다 답을 한 줄에 하나씩 출력한다. 1번, 2번, 3번 쿼리는 아무것도 출력하지 않는다.