길이가 N인 수열 A₀, A₁, ..., A_N-1이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. (0 ≤ A_i < 2³²)</p>

• 1 p v: A_p의 앞에 v를 추가한다. p가 A의 길이와 같은 경우에는 가장 마지막에 추가하는 것이다. (0 ≤ p ≤ A의 길이, 0 ≤ v < 2³²)
• 2 p: A_p를 제거한다. (0 ≤ p < A의 길이)
• 3 p v: A_p를 v로 바꾼다. (0 ≤ p < A의 길이, 0 ≤ v < 2³²)
• 4 l r k: l ≤ i ≤ r에 대해서 (ΣA_i × (i - l + 1)^k) mod 2³²를 구한 다음 출력한다. (0 ≤ k ≤ 10)

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 A₀, A₁, ..., A_N-1이 주어진다.

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

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

출력 형식

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

예제 입력

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

예제 출력

6
26
40
4