구간 합 구하기 K

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

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

• 1 S1 E1 S2 E2 ... SK EK : 1이상 K이하를 만족하는 모든 정수 i에 대해서, Ai 값이 Si 이상이면서 E**i 이하를 모두 만족하는 V[A1, A2, ... , AK]들의 합을 출력한다.
• 2 B1 B2 ... Bk X : V[B1, B2, ... , Bk]를 X로 변경한다.

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

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

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

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

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