题目背景

Mirko 和 Slavko 都将空闲时间花在玩多边形上和观看 The Biggest Loser 上。

题目描述

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 oposite sides (two sides are opposite if there are $\dfrac N2 - 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?

输入格式

第一行，一个整数 $T$，它用作生成 Mirko 查询的参数。 该数字只可以是 $0$ 或 $1$。

第二行，一个正整数 $n$。

第 $3 \sim n + 2$ 行，每行 $2$ 个正整数 $x_i, y_i$ 。表示多边形的一个顶点。顶点是按逆时针顺序给出的，没有三个连续的顶点是共线的。

第 $n + 3$ 行，一个正整数 $q$。

接下来 $q$ 行，每行都有两个整数 $a_i, b_i$，它们用作在第 $i$ 个 Mirko 查询中生成点的参数。$x_i$ 等于 Mirko 查询的第 $i$ 个（含 $i$ 点）在平面彩色部分上的点数。 当然，$x_0 = 0$。然后，应将 Mirko 第 $i$ 个查询的点生成为：

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

其中 $\oplus$ 代表按位异或运算。

输出格式

如果 Mirko 查询的第 $i$ 个点位于平面的有色部分，则输出的第 $i$ 行为 $\tt DA$。 否则，第 $i$ 行为 $\tt NE$。

题目大意

Mirko 最近绘制了一个具有偶数个顶点 $n$ 的凸多边形。

Slavko 选出了每组对边（如果两个边之间有 $\dfrac{n}{2}-1$ 边，则这两个边对边），画出位于这些边上的直线，并将它们与位于它们之间、包含多边形的平面部分一起涂上颜色。

最终，Mirko 选择了 $q$ 个点，并决定向 Slavko 询问，问他每个点是否位于有色或无色部分。

The Biggest Loser 节目即将开始，Slavko 没有时间回答 Mirko 的问题。你能帮她吗？

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

提示

数据规模及约定

本题采用捆绑测试。 | Subtask 编号 | 分值 | 数据范围 | | :-----------: | :-----------: | :-----------: | | $1$ | $20$ | $1 \le n, q \le 2000$，$T = 0$| | $2$ | $30$ | $1 \le n, q \le 10^5$，$T = 0$| | $3$ | $60$ | $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}$。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2019-2020 CONTEST #2 T5 Zvijezda。