Tudor decided to build a rectangular pen for his goats. Unfortunately, he forgot about a classic problem when it comes to owning goats - dealing with goat poop.
Goats poop in rectangles. Formally, Tudor's pen has vertices at and , and the poop for his goats lies exactly on every point inside and on the sides of the axis-aligned rectangle with vertices at and where and and the vertices are at lattice points. Note that the rectangle may have zero area, and could even be a single point.
Tudor has poop detectors that he can place anywhere in the field. Each poop detector can be placed at a lattice point and, when turned on, will report the minimum Manhattan distance to any point inside the rectangle with poop.
Help Tudor determine the area of his pen that is covered in poop.
Constraints
There are three subtasks. The subtasks are cumulative - a solution that passes subtask should pass subtask and therefore we will short-circuit your submission on the first test case it fails.
Subtask 1
Subtask 2
Subtask 3
Input/Output Specification
The first line contains a single positive integer, . You will need to solve independent instances of this problem.
When solving a new instance of the problem, Tudor gives you new poop detectors. You do not need to use all of them. You may not use unused poop detectors from previous instances. You are not provided the value of as part of the input to the problem - as the subtasks are cumulative, we guarantee that any solution which would pass a given subtask will also pass all subtasks that precede it.
This is an interactive problem. You may print a query of the form ? k x_1 y_1 ... x_k y_k
on a single line, indicating that Tudor uses
poop detectors at the lattice points for . Each point must be inside or on the border of Tudor's pen.
After printing and flushing the output, you may read in a line of integers representing the minimum Manhattan distance from the lattice
points, in order, to the poop. The problem is non-adaptive - the rectangle is predetermined when the test case begins.
Whenever you are ready to print the area, output the area of the rectangle in the format ! A
, indicating that the area of the rectangle
covered in poop is . After doing so, you may start immediately solving the next instance if any such instance exists.
Otherwise, your program should return immediately.
Make sure that each query or area output is printed on its own line. Failure to properly end each operation with a newline will result in the interactor hanging and a TLE verdict. Note that other failures to adhere to the specifications of the output, including but not limited to proper formatting or flushing, may result in unexpected wrong verdicts. You may read up on flushing here.
If you print something unexpected at any point during the problem, including guessing the area incorrectly,
the interactor will print -1
and stop processing further input.
Sample Interaction
Note that <<<
represents values that you should read from stdin
, and >>>
represents a string that you print to stdout
.
1 <<<
>>> ? 1 0 0
2 <<<
>>> ? 1 2 2
2 <<<
>>> ? 2 0 2 2 0
2 2 <<<
>>> ! 0
Comments