2D Fenwick Tree

Problem Description

You are given $n \times m$ numbers $a_{1, 1}, a_{1, 2}, a_{1, 3}, \dots, a_{1, m}, \dots, a_{n, m}$.

Support $q$ operations:

1. 1 x y d: set $a_{x,y} = d$.
2. 2 x y: query $\sum_{i=1}^x \sum_{j = 1} ^ y a_{i, j}$.

Input Format

The first line contains three integers $n, m, q$ ($1\leq n,m\leq 500,\ q\leq 2 \times 10^5$).

The next $n$ lines each contain $m$ integers $a_{1, 1}, a_{1, 2}, \dots, a_{1, m}, \dots, a_{n, m}$ ($1\leq a_{i, j}\leq 10^9$).

The next $q$ lines each contain an operation of the form 1 x y d or 2 x y, with $1\leq x\leq n, 1\leq y \leq m, 1\leq d\leq 10^9$ guaranteed.

Output Format

For each query, output one line containing the answer.

Sample Input

2 3 5
1 1 4
5 1 4
2 2 3
1 1 1 4
2 1 3
1 2 3 10
2 2 3

Sample Output

16
9
25