Problem F. Fateful snap ≡
| Author: | N. Grebenyuk | Time limit: | 3 sec | |
| Input / output: | interactive | Memory limit: | 256 Mb |
Statement
At the moment T (where T is an integer), Thanos was located in the point X, Y, Z (where X, Y, Z are also integers) and snapped his fingers. A radiation wave with intensity maxIntensity appeared immediately at this point. In rest points of space at this moment radiation was equal to 0.
Radiation wave is an expanding sphere. Radius of sphere increases one unit in one second, for example, it is equal to a after a seconds. At the time a any point of sphere surface (that is any point which distance to X, Y, Z is equal to a) has intensity equal to maxIntensity. Intensity is gradually decreasing in points inside the sphere.
To be more specific, let's consider a point located at the distance dist (dist ≤ a) from the point X, Y, Z. Intensity of radiation in this point is equal to maxIntensity − (a − dist). Intensity of radiation in points outside the sphere is equal to 0.
See the picture below for clarification. In this picture sphere surface with the maximal intensity (maxIntensity) is marked red. The space inside the sphere with gradually decreasing intensity is colored lighter. Notice, that there are limitations to parameter t we consider in this task, and it's guaranteed that maxIntensity is large enough that any point that gets in the sphere in moment t or earlier will never decrease to the intensity 0 or lower.
Tony stark decided to determine the place and the time of the snap of Thanos. He wants to use his chronotunnel he can send sensors with. A sensor can be sent in some specific time t in any point x, y, z. It measures radiation intensity in this point at the moment t, sends result to Tony Stark as a decimal number and burns. Stark has Q sensors in total, and he wants you to help him determine the place and the time of the snap using not more than Q sensor measurements. (Stark has not figured out yet, that he can go back in time and steal sensors from himself).
Output format
To provide the answer print the symbol "!" and then space separated integers T, X, Y, Z. Notice, that "!" and T also should be space separated. You should terminate immediately after printing the answer.
Interaction
It is guaranteed that Q measurements are enough to solve the problem. If your solution uses more than Q sensors, it will get "Wrong answer" for this test.
To send a sensor parameters description your program has to print line "? t x y z" (without quotes), where 0 ≤ t ≤ 3 ⋅ 108 and t, x, y, z are integers. Jury program gives you one decimal value — result of the measurement at time t in the point x, y, z.
At the end of each sensor parameters description and after printing answer you have to print newline character \n and flush output buffer. To flush the buffer you can use (just after printing):
| Language | C++ | Pascal | Java | Python |
| Command | cout.flush() | flush(output) | System.out.flush() | stdout.flush() |
Constraints
0 ≤ T, X, Y, Z ≤ 108
0 ≤ t ≤ 3 ⋅ 108
0 ≤ x, y, z ≤ 108
3 ⋅ 108 < maxIntensity ≤ 109
Q = 250
Sample tests
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|