Bạn được cho lưới ô vuông kích thước ~n \times n~, các hàng được đánh số thứ tự từ ~1~ tới ~n~, các cột được đánh số thứ tự từ ~1~ tới ~n~. Ban đầu các ô trên lưới đều có giá trị bằng ~0~. Sau đó, bạn 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, bạn 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.

Yêu cầu: In ra câu trả lời cho mỗi truy vấn.

Input

• Dòng ~1~: Hai số nguyên ~n~, ~P~ ~(1 \le n \le 10^9; 1 \le P \le 2 \times 10^5)~;

• ~P~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~T_i~, ~W_i~ ~(1 \le T_i \le 2; 1 \le W_i \le n)~;

• Dòng thứ ~P + 2~: Số nguyên ~Q~ ~(1 \le Q \le 2 \times 10^5)~;

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

Output

In ra ~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