This is a run-twice interactive problem.
There is a hurricane brewing in the middle of the Atlantic Ocean and you have some sensors to deploy to track data about the storm, such as wind speeds and trajectory. Over the span of a one-kilometer square, you have placed $$$n$$$ sensors so far, such that each side of the square has at least one sensor on it. The resulting area you can then scan with the sensors is the convex hull of the sensors.
You have one last sensor to place, then you must report the area that you can scan. However, the hurricane is quickly approaching, and with the strength of the hurricane, you know as soon as you get the last sensor in place, you will lose a significant amount of connection to the sensors.
Due to poor planning, you did not write down any of the coordinates of the sensors, and now only have access to one satellite that can communicate with the sensors. The satellite can ping a location within or on a five-kilometer square, however you do not know exactly where the original square is located, only that it is fully within or on the boundaries of the new square. The result of a ping will tell you whether that location is within or on the convex hull of the sensors. Using at most $$$10000$$$ pings, you must determine the area of sensors' convex hull.
This problem will be modeled as a run-twice interactive problem.
First Run
The first line of input consists of the word ADD.
The second line of input consists of a single integer, $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of initial sensors placed.
The following $$$n$$$ lines consist of two integers, $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq x_i, y_i \leq 1000$$$) — the point corresponding to the location of the $$$i$$$-th sensor. It is guaranteed that no two given points will be equal, and that each side of the bounding square will contain at least one point.
You must print two integers $$$x_a$$$ and $$$y_a$$$ ($$$0 \leq x_a, y_a \leq 1000$$$) — the point corresponding to the location of the added sensor.
Second Run
The first line of input consists of the word AREA.
You can make at most $$$10^4$$$ queries by printing QUERY x y ($$$0 \leq x, y \leq 5000$$$), where $$$x$$$ and $$$y$$$ are integers. The interactor will reply with INSIDE if the point is inside (or on) the convex hull of all $$$n+1$$$ sensors, and OUTSIDE otherwise. It is guaranteed that the coordinates of the sensors are integers in the range $$$0$$$ to $$$5000$$$, inclusive, and that their relative positions to each other were not altered. That is, for all $$$i$$$ and $$$j$$$, the vector spanning point $$$i$$$ to point $$$j$$$ is equivalent in both coordinate systems.
Once you have determined the area of the sensors' convex hull, output a single line consisting of AREA A, where $$$A$$$ is an integer corresponding to the twice the area of the convex hull. It can be proven that doubling the area will always result in an integer value.
If at any point in the second run:
The interactor is NOT adaptive. That is, the location of the initial bounding box will be determined before the second pass, and at no point will its location change regardless of what your program does.
ADD 4 0 500 1000 500 500 0 500 1000
500 500
AREA OUTSIDE INSIDE
QUERY 0 0 QUERY 2500 2500 AREA 1000000