Problem Description

Mirko and Slavko are spending their free time playing with polygons and watching a new season of The Biggest Loser. Mirko recently drew a convex polygon with an even number of vertices $N$. Slavko then considered each pair of opposite sides (two sides are opposite if there are $\dfrac{N}{2} - 1$ sides between them), drew straight lines that lie on those sides, and colored them along with the part of the plane that lies between them and contains the polygon. Finally, Mirko found a set of $Q$ points and decided to challenge Slavko to answer for each point whether it lies in the colored or uncolored part of the plane. The new episode of The Biggest Loser is about to start, and Slavko doesn’t have the time to answer Mirko’s queries. Can you help him?

Input Format

The first line contains an integer $T$, which is used as a parameter for generating Mirko's queries. This number can only be $0$ or $1$.

The second line contains a positive integer $n$.

The next $n$ lines, each containing two positive integers $x_i, y_i$, represent a vertex of the polygon. The vertices are given in counterclockwise order, and no three consecutive vertices are collinear.

The $(n + 3)$-th line contains a positive integer $q$.

The next $q$ lines each contain two integers $a_i, b_i$, which are used as parameters for generating the points in Mirko's $i$-th query. The $i$-th point in Mirko's query is generated as:

$$p_i = (a_i \oplus (T \times x^{3}_{i-1}), b_i \oplus (T \times x^{3}_{i-1}))$$

where $\oplus$ represents the bitwise XOR operation.

Output Format

For each of Mirko's queries, output a line containing "DA" if the point lies in the colored part of the plane, or "NE" if it lies in the uncolored part.

Sample Input and Output

Input Sample #1

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

Output Sample #1

DA
NE
DA
NE

Input Sample #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

Output Sample #2

DA
DA
NE
NE
NE
NE

Input Sample #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

Output Sample #3

DA
DA
DA
NE
NE
NE

Notes/Hints

Data Constraints

This problem uses subtask-based scoring.

Additionally, for $100\%$ of the data, $0 \le |x_i|, |y_i| \le 10^9, 0 \le |a_i|, |b_i| \le 2 \times 10^{18}$.

Notes

This problem is scored according to the original COCI settings, with a maximum score of $110$.

The problem is translated from COCI2019-2020 CONTEST #2 T5 Zvijezda.

见题面 Input 部分

见题面 Output 部分