Description

Mirko 和 Slavko 正在通过玩多边形和观看新一季的《The Biggest Loser》来打发空闲时间。Mirko 最近画了一个有偶数个顶点 $N$ 的凸多边形。然后 Slavko 考虑每对相对的边（如果两边之间有 $\frac N2 - 1$ 条边，则它们是相对的），画出位于这些边上的直线，并将它们与包含多边形的平面部分一起着色。最后，Mirko 找到了一组 $Q$ 个点，并决定挑战 Slavko，要求他回答每个点是位于着色部分还是未着色部分。新的《The Biggest Loser》剧集即将开始，Slavko 没有时间回答 Mirko 的查询。你能帮助他吗？

Input Format

第一行，一个整数 $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$ 代表按位异或运算。

Output Format

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

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

Hint

数据规模及约定

本题采用捆绑测试。

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。

题面翻译由 ChatGPT-4o 提供。