D. Herryng
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

As the Lead Exogeologist for the planet Herryng, you are tasked with surveying the "Convex Craters"—mysterious convex geological formations whose vertices align perfectly with the planet's magnetic $$$n \times n$$$ coordinate grid. The survey area spans from $$$(1, 1)$$$ at the bottom-left to $$$(n, n)$$$ at the top-right.

To map the crater, you are equipped with an Ion-Scanning Camera. For any lattice point $$$(x, y)$$$, the camera returns:

  • I if the point is strictly inside the crater.
  • P if the point lies on the perimeter of the crater.
  • X if the point is outside the crater.

Preliminary long-range scans have already confirmed that the coordinates $$$(1, t)$$$ and $$$(n, b)$$$ are perimeter points (P).

The camera is energy-intensive. You are allowed a maximum of $$$7n$$$ scans before the satellite loses its orbital lock.

Once the survey is complete, you must determine how much sealant is required to cover the crater. One "sealent bucket" covers exactly half of a unit square ($$$0.5$$$ units of area). Print the minimum number of paint buckets needed to cover the entire crater.

Input

The first line contains three integers $$$n$$$, $$$t$$$, and $$$b$$$ ($$$2 \le n \le 10^3$$$, $$$1 \le t, b \le n$$$).

Output

When your program is ready to provide the final result, print a single line in the format ! p, where $$$p$$$ represents the minimum number of paint buckets required to cover the crater.

After printing the answer, your program must immediately perform a flush operation and terminate. Do not print an additional newline character between the answer and the flush.

Interaction

To query for a point $$$(x,y)$$$, print "? x y", where $$$1\le x,y\le n$$$. After that, print a line break and do a flush operation.

After making a query, you should read a single character $$$c$$$. If $$$c$$$ is 'I', $$$(x,y)$$$ is inside the polygon. If $$$c$$$ is 'P', $$$(x,y)$$$ is on the perimeter of the polygon. If $$$c$$$ is 'X', $$$(x,y)$$$ is strictly outside the polygon.

If at some moment your program reads 0 from the interactor, it should immediately exit (for example, by calling exit(0)). You will get a "Wrong Answer" in this case, and it means that you asked more than $$$7n$$$ queries, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream. Note that printing an answer does not count as a query.

Your solution will get "Idleness Limit Exceeded" if you don't print anything or forget to flush the output, including for the final answer.

To flush, you can use (just after printing the line break):

  • fflush(stdout) in C++
  • System.out.flush() in Java
  • stdout.flush() in Python
  • flush(output) in Pascal
  • For other languages, see the documentation.
Example
Input
3 1 2
P
P
P
P
I
P
X
P
P
Output
? 1 1
? 1 2
? 1 3
? 2 1
? 2 2
? 2 3
? 3 1
? 3 2
? 3 3
! 7