Chess Knight

Time limit1sMemory limit512 MB

Summary

Interactive task: find a knight's hidden starting square on an 8x8 board using at most 10 move attempts, where each reply says only whether the move stayed on the board.

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

Problem

This is an interactive problem.

The $8 \times 8$ chessboard is numbered with rows 1 to 8 and columns a to h, so that the bottom left corner is a1 and the top right corner is h8.

A knight is on the board, but its starting position is unknown. The knight moves two squares in one direction and one square in a perpendicular direction, and it must stay on the board. A move is specified by first giving the horizontal offset $x$ (positive is right), then the vertical offset $y$ (positive is up).

If the move succeeds, the knight moves to the new square and the judge prints +. If the destination is outside the board, the knight stays where it is and the judge prints -.

Determine the knight's starting position. You may make at most 10 move attempts, whether successful or not.

Examples1

Example 1

Input


+

+

-

-

+

Expected output

? 2 1

? -2 -1

? 2 -1

? -1 2

? 1 2

! a1