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.

Dữ liệu:

• 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~).

Dữ liệu đảm bảo đúng đắn và luôn có kết quả.

Kết quả:

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

Ví dụ:

Sample Input

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

Sample Output

0
2
4

Giải thích:

Ràng buộc:

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