Range Sum Query K

Time limit6sMemory limit512 MB

Summary

Given a K-dimensional array of N^K values, answer box-sum queries over index ranges and apply point assignments.

Level: Medium5 of 10
Topics: Prefix sum, Array
Solved: No attempts yet

Problem

Each position indexed by integers $D_1, D_2, \ldots, D_K$ with every value in the range $1$ to $N$ holds an integer $V[D_1, D_2, \ldots, D_K]$ .

You process $Q$ queries on $V$ . There are two types.

The first type is 1 S_1 E_1 S_2 E_2 ... S_K E_K. For every integer $i$ with $1 \le i \le K$ , print the sum of $V[A_1, A_2, \ldots, A_K]$ over all tuples where $S_i \le A_i \le E_i$ holds for each $i$ .

The second type is 2 B_1 B_2 ... B_K X. Set $V[B_1, B_2, \ldots, B_K]$ to $X$ .

Input

The first line contains $N$ , $K$ , and $Q$ , separated by spaces.

The second line contains the $N^K$ integers assigned to $V$ . The $i$ -th number on this line, counting from 0, is the value at the position V[i // N^(K-1) % N + 1, i // N^(K-2) % N + 1, ..., i // N^0 % N + 1]. Here // is integer division and % is the remainder operator. The operators //, %, and + have the same precedence.

Each of the next $Q$ lines contains one of the two query types described above. At least one query of the first type is given.

Output

For each query of the first type, print the answer on its own line.

Constraints

$20 \le N$
$1 \le K$
$N^K \le 5 \times 10^5$
$Q \le 10^5$
$1 \le S_i, E_i, A_i \le N$
$0 \le V[D_1, \ldots, D_K], X \le 10^5$
All numbers in the input are integers.

Examples3

Example 1

Input

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

Expected output

20
29

Example 2

Input

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

Expected output

400
429

Example 3

Input

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

Expected output