시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 (하단 참고) 512 MB 21 3 3 75.000%

문제

1~N 범위의 정수 D1, D2, ... , DK 에 대해 정수 V[D1, D2, ... , DK]가 배정되어 있다.

V에 대해 Q개의 쿼리를 처리할 것이고, 쿼리는 2가지 쿼리가 존재한다.

  • 1 SESE... SK EK : 1이상 K이하를 만족하는 모든 정수 i에 대해서, Ai 값이 Si 이상이면서 Ei 이하를 모두 만족하는 V[A1, A2, ... , AK]들의 합을 출력한다.
  • 2 BB2 ... Bk XV[B1B2, ... , Bk]를 X로 변경한다.

입력

N, K, Q가 공백을 사이에 두고 한 줄에 주어진다.

2번째 줄에는 V에 배정되어있는 정수 NK개가 주어진다. 2번째 줄의 i번째 수는 V[// NK-1 + 1, i // NK-2 + 1, ..., i // NK-+ 1]을 나타낸다. 2번째 줄의 제일 처음 나오는 수는 0번째 수이다. 즉, i는 0부터 시작한다. '//'연산자는 몫 연산자를 의미하고 '%'연산자는 나머지 연산자를 의미하며 '//', '%', '+' 세 연산자의 연산자 우선순위는 같다.

그 다음 Q개의 줄에는 위에 설명된 2개중 하나의 쿼리가 한 줄에 하나씩 주어진다. (1번 쿼리는 최소 한 개 이상 주어진다)

출력

1번 쿼리가 주어졌을 때, 쿼리에 대한 올바른 값을 한 줄에 하나씩 출력한다.

제한

  • 20 ≤ N
  • 1 ≤ K
  • NK ≤ 5×105
  • Q ≤ 105
  • 1 ≤ Si, Ei, Ai,≤ N
  • 0 ≤ V[D1, D2, ... , DK] , X ≤ 105
  • 입력으로 주어지는 모든 수는 정수이다.

예제 입력 1

20 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 20
2 1 10
1 1 20

예제 출력 1

20
29

예제 입력 2

20 2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 20 1 20
2 1 1 30
1 1 20 1 20

예제 출력 2

400
429

예제 입력 3

20 2 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 20 2 19
2 5 14 7
2 12 9 8
1 1 20 2 20
2 18 1 3
2 14 17 6
1 2 19 2 19
2 13 8 8
2 20 8 3
2 7 1 1
2 13 13 6
2 8 16 2
2 10 19 6
1 2 19 1 19
2 12 16 5
2 17 2 3
1 2 19 2 20
2 3 3 2
2 6 12 4
1 2 20 2 19

예제 출력 3

342
393
342
380
384
390

시간 제한 안내

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

  • Java 8: 8초
  • Java 8 (OpenJDK): 8초
  • Java 11: 8초
  • Kotlin (JVM): 8초
  • Java 15: 8초