Problem F. Fencing the bishop

Author:A. Usmanov   Time limit:1 sec
Input / output:interactive   Memory limit:512 Mb

Statement

This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.

Chess board is a field of 8 by 8 of alternating white and black cells. Columns are indicated by letters from A to H, rows — by digits from 1 to 8. Cell coordinates are encoded as [column][row], for example E2. The cell A1 in the bottom left is black.

There is a bishop on the chess board at some cell of a given color. Recall that the bishop is a piece which can move over diagonals in any direction for any number of cells. The goal is to determine actual position of the bishop by monitoring some rectangular areas of the board.

Your program must make requests of the form "? A B", where A and B — coordinates of two board cells, bottom left and top right of the rectangle you want to monitor. After every request the bishop makes a move and your will receive a reply communicating which of the monitored rectangles contain the bishop after the move.

Your program must determine the bishop position by making no more than 6 requests. It is guaranteed that bishop moves are predetermined and do not depend on requests.

Input format

First line of input contains string color, with value of either white or black — color of the cell initially occupied by bishop.

Interaction protocol

To make a request, your program must output line "? A B", where A, B — strings of two characters, coordinates of the bottom left and top right of the rectangle you want to monitor.

After setting the monitoring bishop moves and jury program replies to your program with the string S of characters 1 or 0 — with i-th characters equals 1, if bishop is inside the i-th monitored rectangle.

When your program determines the current bishop position X, it must output "! X", where X — string of two characters, bishop cell coordinates. After outputting the answer your program must terminate.

If your program makes incorrect query, it will receive "Presentation error" verdict. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.

Every query and final output must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

Language C++ Pascal Java Python
Code cout.flush() flush(output) System.out.flush() stdout.flush()

Constraints

"A1" ≤ A, B, X ≤ "H8"

A ≤ B

Notes on samples

Bishop movements and monitored areas from the first sample are presented on the picture.

Sample tests

No. Standard input Standard output
1
white

0

01

000

0000

00000

100100

? B2 E4

? A4 C7

? A7 B8

? E4 F8

? H4 H8

? G1 H2

! E4
2
black

0

01

? A1 A1

? C3 C3

! C3

0.122s 0.010s 15