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ị;
• \(\ldots\)

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 5000\); \(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 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

• Gồm \(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

Scoring

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