题目描述

译自 COCI 2019/2020 Contest #2 T5「Zvijezda」

小 M 和小 S 正在用多边形游戏和观看新一季的影视剧来消磨时间。小 M 刚刚画了一个含有 $N$ 个顶点的凸多边形。然后小 S 选出各组对边（两条边是对边当且仅当这两条边之间有 $\frac{N}{2}-1$条边），然后沿着这两条边画一条直线，再给这两条直线所夹的区域以及多边形涂上颜色。最后，为了考验小 S，小 M 选出了 $Q$ 个点，让他对于每个点回答这个点是否落在被染过色的区域内。

新一集的影视剧就要开映了，小 S 才没时间玩这种呢，你能帮帮他吗？

输入格式

第一行一个整数 $T$，为生成询问的参数，$T$ 可以为 $0$ 或 $1$。

第二行一个偶数 $N$，表示顶点数。

接下来 $N$ 行每行两个整数 $X_i,Y_i$，表示多边形的各个顶点。以逆时针顺序给出，保证无三点共线。

接下来一个整数 $Q$，表示询问数。

接下来 $Q$ 行每行两个整数 $A_i,B_i$，为生成第 $i$ 个询问的参数。

令 $X_i$ 表示在小 M 的前 $i$ 个询问的点中处在被染色过的区域的点的个数，并且显然 $X_0=0$，那么小 M 的第 $i$ 个询问为 $P_i(A_i\oplus (T\cdot X^3_{i-1}),~B_i\oplus (T\cdot X^3_{i-1}))$，其中 $\oplus$ 表示按位异或。

输出格式

如果小 M 询问的第 $i$ 个点在被染色过的区域内，请在第 $i$ 行输出 DA（克罗地亚语中表示肯定的意思），否则在该行输出 NE（克罗地亚语中表示否定的意思）。

样例 1

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

DA
NE
DA
NE

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

DA
DA
NE
NE
NE
NE

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

DA
DA
DA
NE
NE
NE

本样例中的染色区域同样例 2 中的染色区域，小 M 的询问分别为：$(2,~2),(2,~1),(9,~14),(25,~29),(32,~30)$ 以及 $(30,~17)$。

数据范围与提示

子任务 $1$：该子任务约占总分的 $18\%$，有 $1\le N,Q\le 2000,T=0$；

子任务 $2$：该子任务约占总分的 $28\%$，有 $1\le N,Q\le 10^5,T=0$；

子任务 $3$：该子任务约占总分的 $54\%$，有 $1\le N,Q\le 10^5,T=1$。

对于 $100\%$ 的数据，有 $0\le |X_i|,|Y_i|\le 10^9, 0\le |A_i|,|B_i|\le 2\times 10^{18}$。