Mirko và Slavko đang dành thời gian rảnh rỗi chơi với các đa giác và xem một mùa mới của chương trình The Biggest Loser. Gần đây, Mirko đã vẽ một đa giác lồi với số đỉnh là số chẵn ~N~. Sau đó, Slavko đã xem xét từng cặp cạnh đối diện (hai cạnh đối diện nếu có ~ \frac{N}{2} - 1 ~ cạnh nằm giữa chúng), vẽ các đường thẳng nằm trên các cạnh đó và tô màu chúng cùng với phần mặt phẳng nằm giữa chúng chứa đa giác. Cuối cùng, Mirko đã tìm ra một tập hợp ~Q~ điểm và quyết định thách đố Slavko trả lời cho từng điểm liệu nó nằm trong phần đã tô màu hay phần chưa tô màu của mặt phẳng.

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 câu hỏi của Mirko. Bạn có thể giúp anh ấy không?

Input

• Dòng đầu tiên chứa một số nguyên ~T~ được sử dụng như một tham số để tạo ra các truy vấn của Mirko. Số này có thể là ~0~ hoặc ~1~.
• Dòng thứ hai chứa một số nguyên chẵn ( N ) từ mô tả bài toán.
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa hai số nguyên ~X_i~ và ~Y_i~ ~(0 \leq |X_i|, |Y_i| \leq 10^9)~ đại diện cho một trong những đỉnh của đa giác. Bạn có thể giả định rằng 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 nào thẳng hàng.
• Dòng tiếp theo chứa một số nguyên ~Q~ từ mô tả bài toán.
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên ~A_i~ và ~B_i~ ~(0 \leq |A_i|, |B_i| \leq 2 \times 10^{18})~ được sử dụng làm tham số để tạo ra điểm trong truy vấn thứ ~i~ của Mirko.

Hãy để ~X_i~ bằng số điểm trong số các truy vấn đầu tiên (bao gồm) của Mirko mà nằm trong phần đã tô màu của mặt phẳng. Tự nhiên, ~X_0 = 0~. Điểm của truy vấn thứ ~i~ của Mirko sau đó được tạo ra như sau: ~ P_i = (A_i \oplus (T \cdot X_{i-1}^3), B_i \oplus (T \cdot X_{i-1}^3))~ trong đó ( \oplus ) đại diện cho phép toán xor bitwise.

Output

Dòng thứ ~i~ của đầu ra nên chứa từ ~DA~ (CÓ trong tiếng Croatia) nếu điểm từ truy vấn thứ ~i~ của Mirko nằm trong phần đã tô màu của mặt phẳng. Ngược lại, dòng đó nên chứa từ ~NE~ (KHÔNG trong tiếng Croatia).

Chú thích

• Subtask 1: 20 điểm, ~1 \leq N, Q \leq 2000, T = 0~.
• Subtask 2: 30 điểm, ~1 \leq N, Q \leq 10^5, T = 0~.
• Subtask 3: 60 điểm, ~1 \leq N, Q \leq 10^5, T = 1~.

Sample Input 1

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

Sample Ouput 1

DA
NE
DA
NE

Sample Input 2

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 Ouput 2

DA
DA
NE
NE
NE
NE

Sample Input 3

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 Ouput 3

DA
DA
DA
NE
NE
NE

Giải thích

• Trong test thứ hai

• Trong test thứ ba, các phần đã tô màu của mặt phẳng giống như trong ví dụ thứ hai và các điểm trong các truy vấn của Mirko là: (2, 2), (2, 1), (9, -14), (25, 29), (-32, 30) và (30, 17).