Let ~A_i~ denote the ~i^\text{th}~ (modulo ~N~) point of our input polygon, and let ~X~ denote the point from Mirko's query.

If ~ccw(A_i, A_{i+1}, X) > 0~, we will write ~1~ on the ~i^\text{th}~ side of our polygon, otherwise we'll write ~0~. Now, we need to answer the question: "Is there a pair of opposite sides such that both of them have ~1~ written on them". Obviously, we cannot check what is written on each of the sides for every query because we would have an ~\mathcal O(NQ)~ algorithm. But, we can get a more efficient algorithm by making some observations.

Observation 1: If two sides have ~1~ written on them, then all sides between them (in one direction) also have ~1~ written on them. We can intuitively see this by imagining that ~X~ is a light source and polygon sides are walls through which the light cannot pass. We can see that illuminated sides have ~0~ written on them. Since all zeroes form an interval on this cyclic array, we can deduce that all ones form an interval as well.

Observation 2: the answer is DA if and only if an interval of ones contains at least ~\frac N 2 + 1~ elements. This is obvious because in ~\frac N 2 + 1~ successive sides, there must be two of them which are opposite.

Now, let's consider an arbitrary side and its opposite side and observe what values are written on them. If both of them have ~1~ written on them, we can immediately output DA. If both of them have ~0~ written on them, we can immediately output NE. If one of them has ~1~ written on it and another one has ~0~ written on it, we can cut the array into two parts, each of which starts with one of the sides we have checked. One part has the form ~111 \dots 000~, and the other one has the form ~000 \dots 111~. In one of them, we want to find the last ~1~ and in the other one, we want to find the first ~1~. This can easily be done using binary search. Now we have found the endpoints of an interval of ones and can easily check if the condition from observation 2 holds.