Interactive Point Inclusion in a Polygon

This is an interactive problem. Given a polygon (P) on a 2D plane with (N) vertices (which are not necessarily convex) enumerated in order as (1 \ldots N), and an extra point indexed as (0), your task is to determine via interaction whether point (0) lies inside (P) or not.

Before the interaction begins, your program reads a line containing two integers (N, Q), where (N) is the number of vertices of the polygon and (Q) is the maximum number of allowed queries.

The only allowed query is:
? a b c: this asks whether the triple of points (a, b, c) are in counterclockwise order. It is guaranteed that (a, b, c) are distinct and each is between (0) and (N) (inclusive). The response is 1 if they are in counterclockwise order, or 0 otherwise.

Once you determine your answer, output a line in the following format:
! x, where (x = 1) means that point (0) is inside (P) and (x = 0) means it is not.

Note: In our offline simulation, the input also includes the coordinates of the points: the next (N) lines contain the coordinates (as two space‐separated integers) of polygon vertices (1) through (N) in order, followed by one more line containing the coordinates of the extra point (0). Use these coordinates and the standard ray-casting algorithm to decide whether point (0) is inside (P) or not. All points are distinct and no three points are collinear. All polygon edges do not intersect.

inputFormat

The first line contains two integers (N) and (Q) ((3 \le N \le 10^5), (Q) is the maximum allowed number of queries).

Then follow (N) lines, each containing two integers (x) and (y), representing the coordinates of the polygon vertices (1, 2, \ldots, N) in order.

Finally, there is one line containing two integers (x) and (y) representing the coordinates of the extra point (0).

outputFormat

After performing your queries (if any), output a single line in the format ! x where (x = 1) indicates that the extra point (0) is inside the polygon, and (x = 0) indicates it is not.

sample

3 100
0 0
4 0
0 4
1 1

! 1