Nam được cho một lưới ô vuông kích thước ~n \times n~, các hàng được đánh số từ ~1~ tới ~n~, các cột cũng được đánh số từ ~1~ tới ~n~. Ban đầu các ô trên lưới đều có giá trị bằng ~0~. Sau đó, Nam sẽ thực hiện ~P~ thay đổi, thay đổi thứ ~i~ có dạng ~(T_i,W_i)~:

• ~T_i=1~, mọi ô ~(x,y)~ sao cho ~1 \le x,y \le W_i~ sẽ thực hiện đảo ngược giá trị, tức là ô có giá trị bằng ~0~ sẽ trở thành ~1~, ô có giá trị bằng ~1~ sẽ trở thành ~0~.

• ~T_i=2~, mọi ô ~(x,y)~ sao cho ~W_i \le x,y \le n~ sẽ thực hiện đảo ngược giá trị.

Sau ~P~ thay đổi, Nam sẽ được cho ~Q~ truy vấn, mỗi truy vấn sẽ yêu cầu tìm giá trị hiện tại của một ô cho trước. Nhiệm vụ của Nam là trả lời các truy vấn ấy.

Input

• Dòng đầu tiên chứa hai số nguyên ~n,P~ ~(1 \le n \le 10^9, 1 \le P \le 2 \cdot 10^5)~ tương ứng với kích thước lưới vuông và số thay đổi trên lưới.

• Trong ~P~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~T_i~ ~(1 \le T_i \le 2)~, ~W_i~ ~(1 \le W_i \le n)~ như mô tả của đề bài.

• Dòng thứ ~P+2~ chứa số nguyên ~Q~ ~(1 \le Q \le 2 \cdot 10^5)~ là số truy vấn bạn cần trả lời.

• Trong ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~X_i,Y_i~ ~(1 \le X_i,Y_i \le n)~ tương ứng ô bạn cần tìm giá trị.

Output

Ghi trên ~Q~ dòng, dòng thứ ~i~ là câu trả lời của bạn đối với truy vấn thứ ~i~.

Scoring

Sample Input 1

7 4
1 2
2 5
1 6
2 1
3
1 1
6 5
4 3

Sample Output 1

1
1
0