题目背景

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

题目描述

Mirko 最近绘制了一个具有偶数个顶点 $n$ 的凸多边形。Slavko 考虑了每对相对的边（如果两个边之间有 $\dfrac{n}{2}-1$ 边，则这两个边是相对的），画出位于这些边上的直线，并对它们以及位于它们之间并包含多边形的那部分平面进行着色。

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

《大输家》节目即将开始，Slavko 没有时间回答 Mirko 的问题。你能帮她吗？

输入格式

第一行，一个整数 $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$。

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。