Cho bản đồ kho báu có dạng bảng chữ nhật ~n \times m~, các dòng được đánh số từ ~1~ đến ~n~ và các cột được đánh số từ ~1~ đến ~m~. Ô ở dòng thứ ~i~, cột thứ ~j~ của bản đồ chứa một kho báu có giá trị ~a_{i, j}~. Cho ~q~ truy vấn thuộc một trong hai loại:

1. Cho ~x, y, z~, gán ~a_{x, y} \leftarrow z~.

2. Cho ~i, j, d~, tính tổng giá trị tất cả các kho báu có khoảng cách Manhattan~^\dagger~ với ô ~(i, j)~ không quá ~d~.

Yêu cầu: Với mỗi truy vấn loại 2, in ra tổng giá trị cần tìm.

~\dagger~ Khoảng cách Manhattan giữa hai số ~(i, j)~ và ~(x, y)~ là ~|i - x| + |j - y|~.

Input

Dòng đầu tiên chứa ba số nguyên ~n, m, q~ là kích thước bản đồ và số truy vấn.

Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m}~ (với ~0 \leq a_{i, j} \leq 10^9~) là giá trị của các ô kho báu trên dòng thứ ~i~.

Trong ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên mô tả một truy vấn:

• Với truy vấn loại 1, bốn số nguyên đó là ~1 \space x \space y \space z~ (với ~1 \leq x \leq n~, ~1 \leq y \leq m~ và ~0 \leq z \leq 10^9~).

• Với truy vấn loại 2, bốn số nguyên đó là ~2 \space i \space j \space d~ (với ~1 \leq i \leq n~, ~1 \leq j \leq m~ và ~0 \leq d \leq n + m - 2~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~) số điểm: ~1 \leq n, m \leq 100~; ~1 \leq q \leq 1000~.

• Subtask ~2~ (chiếm ~80\%~) số điểm: ~1 \leq n, m \leq 500~; ~1 \leq q \leq 10^5~.

Sample Input 1

3 4 3
3 1 2 1
9 8 7 6
2 7 5 1
2 2 3 1
1 2 1 1
2 1 1 3

Sample Output 1

28
32