즈비예즈다

미르코와 슬라브코는 여가 시간에 다각형을 가지고 놀면서 새 시즌의 The Biggest Loser를 보고 있다.

미르코는 최근 꼭짓점 개수 $N$이 짝수인 볼록 다각형을 그렸다. 이어서 슬라브코는 마주 보는 변의 쌍을 모두 살펴보았다. 두 변 사이에 $N/2 - 1$개의 변이 있으면 두 변은 마주 보는 것이다. 슬라브코는 각 쌍에 대해 그 변들이 놓인 직선을 그었다. 그리고 이 직선들과, 두 직선 사이에 있으면서 다각형을 포함하는 평면 부분을 색칠했다.

미르코는 $Q$개의 점을 고르고, 각 점이 색칠된 부분에 있는지 색칠되지 않은 부분에 있는지 슬라브코에게 맞혀 보라고 했다.

첫 줄에는 정수 $T$가 주어진다. $T$는 미르코의 질의를 생성할 때 쓰는 매개변수이며, 0 또는 1이다.

둘째 줄에는 짝수 정수 $N$이 주어진다.

다음 $N$개의 줄에는 다각형의 꼭짓점을 나타내는 두 정수 $X_i$, $Y_i$ ($0 \le |X_i|, |Y_i| \le 10^9$)가 한 줄에 하나씩 주어진다. 꼭짓점은 반시계 방향 순서로 주어지며, 연속한 세 꼭짓점은 한 직선 위에 있지 않다.

다음 줄에는 질의의 개수 $Q$ ($1 \le Q \le 10^5$)가 주어진다.

다음 $Q$개의 줄에는 두 정수 $A_i$, $B_i$ ($0 \le |A_i|, |B_i| \le 2 \times 10^{18}$)가 한 줄에 하나씩 주어진다. 이 값들은 $i$번째 질의의 점을 만드는 데 쓰인다.

$X_i$는 처음 $i$개의 질의 점(자기 자신 포함) 가운데 색칠된 부분에 놓인 점의 개수이며, $X_0 = 0$이다. $i$번째 질의의 점은 다음과 같이 만든다.

$P_i = \left(A_i \oplus \left(T \times (X_{i-1})^3\right),\ B_i \oplus \left(T \times (X_{i-1})^3\right)\right)$

여기서 $\oplus$는 비트 단위 XOR 연산이다.

$i$번째 질의의 점이 색칠된 부분에 있으면 "DA"(크로아티아어로 YES)를, 그렇지 않으면 "NE"(크로아티아어로 NO)를 출력한다.

두 번째 예제에 대한 설명:

세 번째 예제에 대한 설명: 색칠된 부분은 두 번째 예제의 것과 같다. 미르코의 질의 점은 $(2, 2)$, $(2, 1)$, $(9, -14)$, $(25, 29)$, $(-32, 30)$, $(30, 17)$이다.