Tăng bảng

Thao tác tăng hình nón đối xứng của một dãy số $X_1, X_2, X_3, \ldots, X_{N-2}, X_{N-1}, X_N$ được thực hiện như sau:

• Tăng $X_1$ và $X_N$ lên 1 đơn vị;
• Tăng $X_2$ và $X_{N-1}$ lên 2 đơn vị;
• Tăng $X_3$ và $X_{N-2}$ lên 3 đơn vị;
• …

Ví dụ 1:

Ví dụ 2:

Cho một bảng hình vuông A có $N$ dòng, $N$ cột. Các dòng được đánh số từ 1 tới $N$ theo thứ tự từ trên xuống dưới và các cột được đánh số từ 1 tới $N$ theo thứ tự từ trái qua phải. Ô ở dòng thứ $i$, cột thứ $j$ được gọi là ô $A(i, j)$. Ban đầu tất cả các ô đều có giá trị bằng 0.

Thực hiện $T$ thao tác tăng hình nón đối xứng trên bảng A, mỗi thao tác có cấu trúc như sau: gồm bốn số nguyên dương $k, rc, x, y$ ($k = 1$ hoặc $k = 2$) có ý nghĩa:

• Khi $k = 1$, thực hiện tăng hình nón đối xứng trên dòng $rc$ với dãy số gồm các số từ $A(rc, x)$ đến $A(rc, y)$;
• Khi $k = 2$, thực hiện tăng hình nón đối xứng trên cột $rc$ với dãy số gồm các số từ $A(x, rc)$ đến $A(y, rc)$.

Yêu cầu: cho kích thước bảng, $T$ thao tác tăng và $Q$ câu hỏi. Mỗi câu hỏi có ý nghĩa: tìm giá trị của một ô của bảng sau khi thực hiện $T$ thao tác.

Vào từ tệp văn bản ITABLE.INP có cấu trúc:

• Dòng đầu tiên gồm hai số nguyên dương $N$ và $T$ là kích thước của bảng và số thao tác tăng. ($N \le 5000; T \le 10^5$)
• $T$ dòng sau, mỗi dòng gồm bốn số nguyên dương $k, rc, x, y$ mô tả thao tác tăng lên dòng hoặc cột của bảng. ($k = 1$ hoặc $k = 2; rc, x, y \le N$)
• Dòng tiếp theo gồm số một số nguyên dương $Q$ là số ô cần tìm giá trị. ($Q \le 10^5$)
• $Q$ dòng sau, mỗi dòng chứa hai số nguyên dương $u, v$ có ý nghĩa là cần tìm giá trị của ô $A(u, v)$. ($u, v \le N$)

Mỗi số cách nhau một dấu cách. Dữ liệu đảm bảo đúng đắn và luôn có kết quả.

Ghi ra tệp văn bản ITABLE.INP gồm $Q$ dòng, mỗi dòng in ra giá trị của một ô tương ứng.

• Có 50% số test tương ứng với số điểm có với $T \le 5000$;
• Có 30% số test khác tương ứng với số điểm có với $Q \le 500$;
• Có 20% số test còn lại tương ứng với số điểm không có giới hạn gì thêm.