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 nhập vào từ file văn bản ITABLE.INP:

• 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≤5000; \ T≤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≤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≤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≤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ả.

Kết quả ghi ra file văn bản ITABLE.OUT:

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

Ví dụ

Input

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

Output

0
2
4

Giải thích:

Giới hạn

• Có ~50\%~ số test tương ứng với số điểm có với ~T≤5000;~
• Có ~30\%~ số test khác tương ứng với số điểm có với ~Q≤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~.~