Mirko 和 Slavko 正在利用闲暇时间研究多边形，并观看新一季的《超级减肥王》（The Biggest Loser）。Mirko 最近画了一个具有偶数个顶点 $N$ 的凸多边形。Slavko 随后考虑了每一对对边（如果两条边之间有 $\frac{N}{2} - 1$ 条边，则称它们是对边），画出了包含这些边的直线，并将这两条直线以及它们之间包含该多边形的平面区域涂上颜色。最后，Mirko 找到了一个包含 $Q$ 个点的集合，并决定挑战 Slavko，让他回答每个点是位于涂色区域还是未涂色区域。

新一季的《超级减肥王》即将开始，Slavko 没有时间回答 Mirko 的询问。你能帮帮他吗？

输入格式

第一行包含一个整数 $T$，它是用于生成 Mirko 询问的参数。该数字只能为 $0$ 或 $1$。

第二行包含一个偶数 $N$，表示多边形的顶点数。

接下来的 $N$ 行，每行包含两个整数 $X_i, Y_i$（$0 \le |X_i|, |Y_i| \le 10^9$），表示多边形的一个顶点。你可以认为顶点是按逆时针顺序给出的，且任意连续三个顶点都不共线。

下一行包含一个整数 $Q$，表示询问的数量。

接下来的 $Q$ 行，每行包含两个整数 $A_i, B_i$（$0 \le |A_i|, |B_i| \le 2 \cdot 10^{18}$），它们是用于生成 Mirko 第 $i$ 次询问中点坐标的参数。

设 $X_i$ 为 Mirko 的前 $i$ 次（含第 $i$ 次）询问中，落在涂色区域内的点的数量。显然，$X_0 = 0$。Mirko 第 $i$ 次询问的点 $P_i$ 应按如下方式生成：

$$P_i = (A_i \oplus (T \cdot X_{i-1}^3), B_i \oplus (T \cdot X_{i-1}^3))$$

其中 $\oplus$ 表示按位异或（xor）运算。

输出格式

输出的第 $i$ 行应包含单词 "DA"（克罗地亚语中的“是”），如果 Mirko 第 $i$ 次询问的点位于平面的涂色部分。否则，第 $i$ 行应包含单词 "NE"（克罗地亚语中的“否”）。

子任务

样例

输入样例 1

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

输出样例 1

DA
NE
DA
NE

输入样例 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

输出样例 2

DA
DA
NE
NE
NE
NE

输入样例 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

输出样例 3

DA
DA
DA
NE
NE
NE

说明

样例 2 说明

样例 3 说明

平面的涂色部分与样例 2 相同，Mirko 询问的点分别为：$(2, 2)$，$(2, 1)$，$(9, -14)$，$(25, 29)$，$(-32, 30)$ 和 $(30, 17)$。