NGUỒN: ĐỀ THI HSG HÀ NỘI 2020 - 2021
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,…,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ị;
• \(...\)
  

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.

INPUT

• 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 \leq 5 \times 10^ 3 ; T \leq 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 \leq 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 \leq 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 \leq 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ả.

OUTPUT

• In ra \(Q\) dòng, mỗi dòng in ra giá trị của một ô tương ứng.

Example

4 2
1 2 1 4
2 3 1 3
3
1 1 
2 2 
2 3

0
2
4

Ràng buộc

• Subtask \(1\) (\(50\%\) số test): Có \(T\) \((T\leq 5000)\);
• Subtask \(2\) (\(30\%\) số test): Có \(Q\) \((Q\leq 500)\);
• Subtask \(3\) (\(20\%\) số test): Không có ràng buộc gì thêm.