Mirko và Slavko đang dành thời gian rảnh để chơi với các đa giác và xem phần mới của The Biggest Loser (tên một bộ phim). Mirko đã vẽ một đa giác lồi ~N~ đỉnh (~N~ là số chẵn). Slavko sẽ đánh giá các cặp cạnh đối diện nhau (hai cạnh được coi là đối diện nhau nếu giữa chúng có ~\frac{N}{2}-1~ cạnh khác), sau đó Slavko kéo dài tất cả các cạnh cặp cạnh đối diện nhau và tô màu phần mặt phẳng nằm giữa chúng và chứa đa giác. Cuối cùng, Mirko đã tìm ra tập gồm ~Q~ điểm và quyết định thử thách Slavko, hãy cho biết mỗi điểm nằm trong phần được tô màu hay không được tô màu của mặt phẳng. (Các bạn có thể đọc qua test ví dụ và hình vẽ để hiểu rõ hơn)

Tập mới của The Biggest Loser sắp bắt đầu và Slavko không có thời gian để trả lời các truy vấn của Mirko. Bạn có thể giúp Slavko được không?

Input

Dòng đầu tiên chứa một số nguyên ~T~ có thể là ~0~ hoặc ~1~.

Dòng thứ hai chứa một số nguyên ~N~ chẵn.

Mỗi dòng trong số ~N~ dòng tiếp theo chứa hai số nguyên ~Xi, Yi~ ~(0 ≤ | Xi |, | Y i | ≤ 10^9)~ là các đỉnh của đa giác. Các đỉnh được cho theo thứ tự ngược chiều kim đồng hồ và không có ba đỉnh liên tiếp thẳng hàng.

Dòng tiếp theo chứa một số nguyên ~Q~.

Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên ~Ai, Bi~ ~(0 ≤ | Ai |, | Bi | ≤ 2\times10^{18})~ được sử dụng như tham số để tạo điểm trong truy vấn thứ ~i~ của Mirko.

Gọi ~X_i~ là số điểm trong ~i~ truy vấn đầu tiên nằm trong phần mặt phẳng được tô màu. Đương nhiên, ~X_0= 0~. Điểm của truy vấn thứ ~i~ của Mirko sau đó sẽ được tạo là:

~P_i = ( A_i ⊕ (T \times X_{i-1}^3), B_i ⊕ (T \times X_{i-1}^3)) ~

trong đó ⊕ đại diện cho phép toán XOR.

Output

Dòng thứ ~i~ phải chứa từ "DA" nếu điểm được tạo ra từ truy vấn thứ i của Mirko nằm trong phần mặt phẳng được tô màu. Ngược lại, dòng thứ ~i~ phải chứa từ "NE".

Sample Input1

0
4
1 1
5 1
4 3
2 2
4
3 2
2 4
6 2
4 5

Sample Output1

DA
NE
DA
NE

Sample Input2

0
6
-1 -1
2 -1
3 3
2 4
1 4
-2 1
6
2 2
3 0
1 -6
2 6
-5 5
5 10

Sample Output2

DA
DA
NE
NE
NE
NE

Sample Input3

1
6
-1 -1
2 -1
3 3
2 4
1 4
-2 1
6
2 2
3 0
1 -6
2 6
-5 5
5 10

Sample Output3

DA
DA
DA
NE
NE
NE

Giải thích cho ví dụ 2:

Giải thích cho ví dụ 3:

Phần được tô màu giống ví dụ 2 và các điểm được tạo ra từ truy vấn của Mirko: ~(2,2), (2,1), (9,-14), (25,29), (-32,30)~ và ~(30,17)~.

Subtask

• ~6~ test ~1 \le N,Q \le 2000,~ ~T=0~

• ~9~ test ~1 \le N,Q \le 10^5,~ ~T=0~

• Số test còn lại ~1 \le N,Q \le 10^5,~ ~T=1~