Smallest and Largest Subarray

問題文

この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。
また、問題文のパラメータは $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$ つずつ求めてください。

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

数列の辞書順とは

数列 $S = (S_1, S_2, \cdots, S_{|S|})$ が数列 $T = (T_1, T_2, \cdots, T_{|T|})$ より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。

1. $|S| \lt |T|$ かつ $(S_1, S_2, \cdots S_{|S|}) = (T_1, T_2, \cdots, T_{|S|})$.
2. ある整数 $1 \le i \le \min(|S|, |T|)$ が存在して, 下記のすべてが成り立つ.
   • $(S_1, S_2, \cdots, S_{i - 1}) = (T_1, T_2, \cdots, T_{i - 1})$.
   • $S_i$ が $T_i$ より（数として）小さい.

制約

• $\color{red}N = 1000$
• $\color{red}Q = 1500$
• $1 \leq A_i \leq N \enspace (1 \leq i \leq N)$
• $A_i$ は整数

入出力

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

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

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

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

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

ここで、 $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$ のとき、不正な出力をしたか、質問回数が $Q$ 回を超えた。

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

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

ただち、この出力は質問回数に計上されません。また、答えが複数あるとき、それらのうちいずれを出力しても正解と判定されます。

その後、ただちにプログラムを終了してください。

注意点

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

入出力例

入出力例 1

$N = 3, Q = 5$ であり、ジャッジシステムが $A = (2, 3, 1)$ を隠し持っているとします。その場合、対話の一例は以下の通りです。

なお、この例は制約を満たさないので、ジャッジには含まれないことに注意してください。

入力	出力	説明
3 5		$N, Q$ が入力されます。
	? 2 2 3 3	命題「$(A_2)$ は $(A_3)$ より辞書順で小さい」の真偽を質問します。
0		$(3)$ は $(1)$ より辞書順で小さくない（大きいまたは等しい）ため偽です。応答として $0$ が与えられます。
	? 1 3 2 3	命題「$(A_1, A_2, A_3)$ は $(A_2, A_3)$ より辞書順で小さい」の真偽を質問します。
1		$(2, 3, 1)$ は $(3, 1)$ より辞書順で小さいため真です。応答として $1$ が与えられます。
	? 1 2 3 3	命題「$(A_1, A_2)$ は $(A_3)$ より辞書順で小さい」の真偽を質問します。
0		$(2, 3)$ は $(1)$ より辞書順で小さくない（大きいまたは等しい）ため偽です。応答として $0$ が与えられます。
	! 3 3 2 3	$A$ の連続部分列のうち辞書順で最小のものが $(A_3)$、最大のものが $(A_2, A_3)$ であると解答します。