Hot and Cold

Time limit3sMemory limit1024 MB

Summary

Find a hidden integer point with coordinates up to 10^6 in at most 64 visits, using only closer, further, or same-distance answers.

Level: Medium6 of 10
Topics: Binary search, Geometry
Solved: No attempts yet

Problem

This is an interactive problem.

After emigrating to another country, little Hanna found that playing "Hot and cold" became harder, because she does not understand the hint phrases. You are to write a helping program for her.

The playground is a rectangle, and the treasure is hidden at some point with integer coordinates between 0 and $10^6$ , inclusive. Hanna visits several points with valid coordinates. If the visited point contains the treasure, she receives the phrase "Found!" in the local language, which is denoted by an exclamation mark.

Otherwise, for each visited point except the first one, Hanna receives a phrase stating whether she is "Closer", "Further", or "At the same distance" from the treasure compared to the previous point. Distances are Euclidean. After the first visited point, if there is no treasure there, Hanna receives "Not found" in the local language.

Your program must help Hanna find the treasure by visiting at most 64 points.

Examples2

Example 1

Input


Tabilmadi

Daha yakin

Daha yakin

Sama distanco

Dalej

Znaydeno!

Expected output

Example 2
Input
```
You are lucky today!
```
Expected output
```
777777 777777
```