問題文

この問題はリアクティブ形式の（ジャッジ側のプログラムと対話的に実行する必要がある）問題です。

$xy$ 平面内の点 $Q$ に対し、$Q$ の $x$ 座標と $y$ 座標をそれぞれ $x(Q)$ と $y(Q)$ と書き表します。

$xy$ 平面内の $2$ 点 $Q_0$ と $Q_1$ の $L^1$ 距離（マンハッタン距離）

$\displaystyle |x(Q_0) - x(Q_1)| + |y(Q_0) - y(Q_1)| $

を $d(Q_0,Q_1)$ と書き表します。

最初に正整数 $T$ と $xy$ 平面内の $2$ 個の格子点 $P_0$ と $P_T$ が与えられます。

格子点大好きbotは格子点が大好きなbotです。

格子点大好きbotは時刻 $0$ から $T$ まで $xy$ 平面上を移動しており、$T$ 以下の非負実数 $t$ に対し時刻 $t$ における格子点大好きbotの座標を $P(t)$ と置きます。

あなたは格子点大好きbotから以下の情報を得ました。

• $P(0) = P_0$ かつ $P(T) = P_T$ である。（つまり格子点大好きbotは $P_0$ から $P_T$ まで運動する）
• $T$ 以下の任意の非負整数 $t$ に対し、$P(t)$ は格子点である。（つまり $P(0), P(1), \ldots, P(T)$ は全て格子点である）
• 格子点大好きbotの移動は、$x$ 軸または $y$ 軸に平行な線分上の速さ $1$ の等速直線運動と静止運動をそれぞれ $0$ 個以上の有限個繋げたものである。（各運動時間が整数とは限らないことに注意する）

あなたはそれらの情報をもとに、格子点大好きbotが時刻 $0$ から $T$ の間に $P_0$ と $P_T$ から $L^1$ 距離に関して等距離である点を少なくとも一度は通っていること、すなわち

$ 0 \leq t \leq T \land d(P(t),P_0) = d(P(t),P_T) $

を満たす実数 $t$ が存在することを推測しました。以下このような $t$ を良い時刻と呼びます。

そこで、以下の一連のやり取り（以下、質問と呼ぶ）を $0$ 回以上 $100$ 回以下の好きな回数行います。

1. まずあなたが $T$ 以下の非負整数 $t$ を選び、時刻 $t$ における格子点大好きbotの座標 $P(t)$ を尋ねる。
2. 続いて格子点大好きbotが格子点 $P(t)$ の座標を答える。

その後、良い時刻が存在するか否かを判定し、存在する場合は良い時刻を $1$ つ求めてください。

入出力

最初に $T, x(P_0), y(P_0), x(P_T), y(P_T)$ が標準入力から半角空白区切りで $1$ 行で与えられます。

$T$ $x(P_0)$ $y(P_0)$ $x(P_T)$ $y(P_T)$

その後で $0$ 回以上 $100$ 回以下の好きな回数質問をしてください。質問は標準入出力を用いて以下の形式で行います：

1. まず?と $T$ 以下の非負整数 $t$ を半角空白区切りで $1$ 行で出力してください。

? $t$

2. 続いて $x(P(t)), y(P(t))$ が半角空白区切りで $1$ 行で与えられます。

$x(P(t))$ $y(P(t))$

次にあなたはこの問題に対する答えを標準出力に以下の形式で出力してください：

• 良い時刻が存在しないならば、! NaNと出力してください。

! NaN

• 良い時刻が存在するか否かを判定し、存在する場合は!と良い時刻の一例 $t$ を超えない最大の整数 $\lfloor t \rfloor$ を半角空白区切りで $1$ 行で出力してください。

! $\lfloor t \rfloor$

最後に改行してください。

制約

入力では与えられませんが、$P(t)$ は以下の制約を満たします：

• $T$ 以下の非負実数 $t$ に対する $P(t)$ は全ての質問の前に確定しており、すなわち質問の前後で変化しない。
• $P(0) = P_0$ かつ $P(T) = P_T$ である。
• $T$ 以下の任意の非負整数 $t$ に対し、$P(t)$ は格子点である。
• 格子点大好きbotの移動は、$x$ 軸または $y$ 軸に平行な線分上の速さ $1$ の等速直線運動と静止運動をそれぞれ $0$ 個以上の有限個繋げたものである。

入力は以下の制約を満たします：

• $T$ は $1 \leq T \leq 10^3$ を満たす整数である。
• $x(P_0)$ は $-10^3 \leq x(P_0) \leq 10^3$ を満たす整数である。
• $y(P_0)$ は $-10^3 \leq y(P_0) \leq 10^3$ を満たす整数である。
• $x(P_T)$ は整数である。
• $y(P_T)$ は整数である。
• $T$ 以下の任意の非負整数 $t$ に対し、時刻 $t$ における格子点大好きbotの座標を尋ねた際の返答である入力 $x(P(t)), y(P(t))$ は以下を満たす。
• $x(P(t))$ は $- 2 \times 10^3 \leq x(P(t)) \leq 2 \times 10^3$ を満たす整数である。
• $y(P(t))$ は $- 2 \times 10^3 \leq y(P(t)) \leq 2 \times 10^3$ を満たす整数である。

注意

リアクティブ形式の問題に慣れてない方は、リアクティブ形式の問題についてのまとめも参考にしてください。

この問題において、以下の指示に従っていない提出のジャッジ結果は保証しません：

• 出力は指定された形式に厳格に従ってください。例えば余計な空白を入れたりしないでください。
• 出力を行うたびに末尾に改行を入れて標準出力をflushしてください。
• この問題に対する答えを出力した後はプログラムをすぐに終了させてください。

サンプル

3 0 0 2 1

? 1

1 0

? 2

2 0

! 1