시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 6 3 60.000%

문제

길이가 N인 수열 A0, A1, ..., AN-1이 주어진다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오. (0 ≤ Ai < 232)

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

입력

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

둘째 줄에는 A0, A1, ..., AN-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

힌트

출처