問題文

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。
また、問題文中のパラメータは $N = 1000, ~ Q = 1500$ で固定されています。

整数 $N, Q$ が与えられます。
ジャッジシステムは、長さ $N$ の整数列 $A = (A_1, A_2, \cdots, A_N)$ を隠し持っています。

あなたは $A$ の要素の値を直接知ることはできません。
その代わりに、ジャッジシステムに対して質問を $Q$ 回まで行うことができます。$1$ 回の質問は以下の通りです。

質問：$1 \le l \le r \le N$ かつ $1 \le l' \le r' \le N$ を満たす整数 $l, r, l', r'$ を選び、以下の命題の真偽を尋ねる。

• $(A_l, A_{l + 1}, \cdots, A_r)$ は $(A_{l'}, A_{l' + 1}, \cdots, A_{r'})$ より辞書順で小さい。

$Q$ 回以下の質問が完了した後、$A$ の連続部分列のうち、辞書順で最小のものの区間と辞書順で最大のものの区間をそれぞれ $1$ つずつ求めてください。

ただし、答えが複数ある場合、いずれを答えても正解と判定されます。

制約

• $N = \color{red}{1000}$
• $Q = \color{red}{1500}$
• $1 \le A_i \le N ~ (1 \le i \le N)$
• $N, Q, A_i$ は整数である。

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

最初に、$N, Q$ を標準入力から受け取ってください。

$N$ $Q$

次に、$A$ のうち辞書順で最大のものの区間と辞書順で最小のものの区間が特定できるまで質問を繰り返してください。

質問は、以下の形式で標準出力に出力してください。 ここで、$l, r, l', r'$ は $1 \le l \le r \le N$ かつ $1 \le l' \le r' \le N$ を満たす整数である必要があります。

? $l$ $r$ $l'$ $r'$

これに対する応答は、次の形式で標準入力から与えられます。

$X$

ここで、$X$ は質問に対する答えとなる整数であり、それぞれ以下のように説明されます。

• $X = 1$ のとき、命題「$(A_l, A_{l + 1}, \cdots, A_r)$ は $(A_{l'}, A_{l' + 1}, \cdots, A_{r'})$ より辞書順で小さい」が真であることを意味する。
• $X = 0$ のとき、命題「$(A_l, A_{l + 1}, \cdots, A_r)$ は $(A_{l'}, A_{l' + 1}, \cdots, A_{r'})$ より辞書順で小さい」が偽であることを意味する。
• $X = -1$ のとき、$l, r, l', r'$ が制約を満たしていないか、質問回数が $Q$ 回を超えたことを意味する。

ジャッジシステムの応答が $-1$ であった場合、既に不正解とみなされています。その場合、ただちにプログラムを終了させてください。

$A$ の連続部分列のうち、辞書順で最小のものが $(A_l, A_{l + 1}, \cdots, A_{r})$ 、辞書順で最大のものが $(A_L, A_{L + 1}, \cdots, A_{R})$ であると特定できたとします。
整数 $l, r, L, R$ を以下の形式で標準出力に出力してください。

ただし、これは質問回数に計上されません。また、答えが複数あるとき、いずれを出力しても正解と判定されます。
その後、ただちにプログラムを終了してください。

! $l$ $r$ $L$ $R$

上記のいずれの形式にも当てはまらない出力をした場合、-1 が標準入力から与えられます。

-1

この場合も不正解とみなされているため、ただちにプログラムを終了させてください。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 解答を出力したら（または -1 を受け取ったら）ただちにプログラムを終了してください。そうしなかった場合、ジャッジ結果は不定です。
• 余計な改行は不正なフォーマットの出力とみなされることに注意してください。

サンプル