Sau khi giải cứu công chúa xinh đẹp BlockyBlock khỏi nanh vuốt quái vật, ngochuy liền được phong thành phò mã sống hạnh phúc bên nàng. Công chúa rất yêu động vật, đặc biệt là loài thỏ. Trong khu Rừng Thiêng mặc dù nguy hiểm nhưng lại là nơi cư ngụ của loài Thỏ Ngọc tuyệt đẹp, có thể coi là Quốc bảo của ByteLand.

Loài Thỏ Ngọc này sinh sôi rất nhanh, nhưng cũng chịu sự nguy hiểm rất lớn từ những loài thú ăn thịt và quái vật trong rừng. Vì vậy công chúa cần biết số lượng Thỏ Ngọc ở từng khu vực để phân bố lực lượng bảo tồn động vật cho hợp lý. Do đó nàng muốn nhờ ngochuy tạo nên một chương trình máy tính có thể kiểm soát được sự tăng trưởng của thỏ trong từng khu vực. Vì khả năng lập trình hạn chế nên một lần nữa ngochuy lại cần nhờ đến sự giúp đỡ của các bạn rồi!

Sơ đồ khu Rừng Thiêng được biểu diễn bằng một lưới ô vuông có kích thước \(M\times N\), được đánh số theo thứ tự từ \(1\) đến \(M\) từ trên xuống dưới và từ \(1\) đến \(N\) từ trái sang phải. Số lượng thỏ ở mỗi khu vực ban đầu được thể hiện bằng số nguyên dương \(r_{x,y}\). Có hai loại thông tin sẽ được nhập vào máy dưới dạng:

1. "\(1\ x\ y\ t\)" - Đội bảo tồn động vật cập nhật vào hệ thống số lượng cá thể thỏ đã thay đổi trong khu vực có tọa độ \((x,\ y)\). Nếu \(t\) dương nghĩa là thỏ đã sinh sôi thêm một số lượng cá thể, và nếu \(t\) âm nghĩa là số lượng cá thể giảm do lượng sinh sôi trong thời gian đó ít hơn lượng chết đi vì bị tấn công bởi các loài ăn thịt. Dữ liệu đảm bảo \(r_{x,y}\) luôn dương ở mọi thời điểm \(\forall x,\ y\).
2. "\(2\ x1\ y1\ x2\ y2\)" - Lệnh yêu cầu in ra tổng số lượng cá thể thỏ trong hệ thống tại thời điểm đó của tất cả các khu vực trong hình chữ nhật có góc trên bên trái có tọa độ \((x1,\ y1)\) và góc dưới bên phải có tọa độ \((x2,\ y2)\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(M,\ N\): kích thước khu rừng;
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa \(N\) số nguyên dương \(r_{i,1},\ r_{i,2},\ldots,\ r_{i,N}\) thể hiện số lượng cá thể thỏ ở từng khu vực;
• Dòng tiếp theo chứa số nguyên dương \(Q\): số lượng truy vấn;
• Cuối cùng là \(Q\) dòng thể hiện các truy vấn, mỗi truy vấn có dạng: "\(1\ x1\ y1\ t\)" hoặc "\(2\ x1\ y1\ x2\ y2\)".

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả trên một dòng.

Ví dụ

Sample input

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

Sample outpuut

37
66

Ràng buộc

• \(1\leq M,\ N\leq1000\);
• \(1\leq Q\leq10^5\);
• \(1\leq r_{x,y}\leq10^9\);
• \(|t|\leq10^9\);
• \(1\leq x1,\ x2\leq M\) và \(1\leq y1,\ y2\leq N\);
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm chỉ có truy vấn loại \(2\).