Thao tác trên bảng

Cấu trúc dữ liệu là nội dung rất quan trọng trong khoa học máy tính. Trong chương trình giảng dạy cho các lớp chuyên Tin, nội dung cấu trúc dữ liệu được đưa vào nhiều chuyên đề. Một bài toán thao tác trên bảng được dùng để kiểm tra khả năng tổ chức dữ liệu và linh hoạt trong xử lí như sau: Cho một bảng số gồm $m$ hàng $n$ cột, các hàng được đánh số từ trên xuống từ $1$ đến $m$, các cột được đánh số từ trái sang phải từ $1$ đến $n$, ô nằm giao giữa hàng $i$ ($1\le i\le m$) và cột $j$ ($1\le j\le n$) gọi là ô $(i,j)$ và có giá trị ban đầu là $a_{ij}$. Cần thực hiện $Q$ thao tác trên bảng số, mỗi thao tác thuộc một trong hai loại:

• Thao tác loại 1 có dạng: $1xyuvw$ có nghĩa là với mỗi ô nằm trong hình chữ nhật có ô trái trên là ô $(x,y)$ và ô phải dưới là ô $(u,v)$ sẽ được cộng thêm $w$;
• Thao tác loại 2 có dạng: $2xyuv$ có nghĩa là cần đưa ra tổng giá trị của các ô nằm trong hình chữ nhật có ô trái trên là ô $(x,y)$ và ô phải dưới là ô $(u,v)$.

Yêu cầu: Thực hiện các thao tác trên bảng số theo kịch bản.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $m,n,Q$ ($m,n\le 500$);
• Dòng thứ $i$ ($1\le i\le m$) trong $m$ dòng sau chứa $n$ số nguyên không âm $a_{i1},a_{i2},\dots ,a_{in}$ ($a_{ij}\le {10}^9$);
• Dòng thứ $k$ ($1\le k\le Q$) trong $Q$ dòng sau mô tả thao tác thứ $k$. Nếu là thao tác loại 1, dòng gồm sáu số nguyên $1,x,y,u,v,w$ ($1\le x\le u\le m$; $1\le y\le v\le n$; $0\le w\le {10}^9$), nếu là thao tác loại 2, dòng gồm năm số nguyên $2,x,y,u,v$ ($1\le x\le u\le m$; $1\le y\le v\le n$).

Dữ liệu ra

In ra một số dòng, mỗi dòng tương ứng là câu trả lời cho thao tác loại 2 lần lượt xuất hiện trong dữ liệu vào.

Ràng buộc

• $1\le m,n\le 500$; $1\le Q\le {10}^5$.
• $0\le a_{ij}\le {10}^9$; $0\le w\le {10}^9$.
• Dữ liệu đảm bảo câu trả lời của mỗi thao tác loại 2 không vượt quá ${10}^{18}$.

Subtasks

Điểm được tính theo từng test.

• Có $30\%$ số lượng test ứng với $30\%$ số điểm thỏa mãn: $Q\le 100$;
• Có $30\%$ số lượng test khác ứng với $30\%$ số điểm thỏa mãn: $Q\le {10}^5$ và tất cả các thao tác loại 1 xuất hiện trước các thao tác loại 2;
• Có $20\%$ số lượng test khác ứng với $20\%$ số điểm thỏa mãn: $Q\le {10}^4$;
• Có $20\%$ số lượng test còn lại ứng với $20\%$ số điểm thỏa mãn: $Q\le {10}^5$.

Ví dụ