시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB127654.545%

문제

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 N/2 − 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?

입력

The first line contains an integer T which is used as a parameter for generating Mirko’s queries. This number can be either 0 or 1.

The second line contains an even integer N from the task description.

Each of the next N lines contains two integers Xi, Yi (0 ≤ |Xi|, |Yi| ≤ 109) which represent one of the polygon’s vertices. You can assume that the vertices are given in the counter clockwise order and that no three successive vertices are collinear.

The next line contains an integer Q (1 ≤ Q ≤ 105) from the task description.

Each of the next Q lines contains two integers Ai, Bi (0 ≤ |Ai|, |Bi| ≤ 2 · 1018) which are used as parameters for generating the point in the i-th of Mirko’s queries.

Let Xi be equal to the number of points in the first i (inclusive) of Mirko’s queries that lie in the colored part of the plane. Naturally, X0 = 0. The point of Mirko’s i-th query should then be generated as:

Pi = (Ai ⊕ (T · (Xi−1)3), Bi ⊕ (T · (Xi−1)3))

where ⊕ represents the bitwise xor operation.

출력

The i-th line of output should contain the word "DA" (YES in Croatian) if the point from i-th of Mirko’s queries lies in the colored part of the plane. Otherwise, the i-th line should contain the word "NE" (NO in Croatian).

서브태스크

번호배점제한
120

1 ≤ N, Q ≤ 2000, T = 0

230

1 ≤ N, Q ≤ 105, T = 0

360

1 ≤ N, Q ≤ 105, T = 1

예제 입력 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

힌트

Clarification of the second example:

Clarification of the third example: The colored parts of the plane are the same as in the second example and the points in Mirko’s queries are: (2, 2), (2, 1), (9, −14), (25, 29), (−32, 30) and (30, 17).

채점 및 기타 정보

  • 예제는 채점하지 않는다.