長方形状のあるグリッドにおいて、上から \(i\) 行目、左から \(j\) 列目に位置するマスを、マス \((i,j)\) と表記します。また、\(r_1\leq r\leq r_2,c_1\leq c\leq c_2\) を満たすマス \((r,c)\) からなる集合を、長方形領域 \((r_1,c_1,r_2,c_2)\) と表します。
長方形状のグリッドが \(N\) 個あります。\(i\) 番目のグリッドは \(H_i\) 行 \(W_i\) 列からなり、はじめ、長方形領域 \((2,2,H_i,W_i)\) に属するすべてのマスが塗りつぶされています。つまり、塗りつぶされていないマスは \(1\) 行目または \(1\) 列目に属するマスのみです。
この \(N\) 個のグリッドの上で、あなたと KowerKoint 君がゲームを行います。ゲームではあなたを先手として 2 人が交互に以下の操作を行います。
先に操作を行えなくなった方が負けで、負けなかった方が勝ちです。 両者は勝ちを目指して最適に操作を行います。
\(N\) 個の問題について答えてください。\(i\) 番目の問題は以下のように表されます。
入力は以下の形式で標準入力から与えられます。
| \(N\) | |
| \(H_1~W_1\) | |
| \(H_2~W_2\) | |
| \(\vdots\) | |
| \(H_N~W_N\) |
入力は以下の制約をすべて満たします。
\(N\) 行出力してください。\(i\) 行目には \(i\) 番目の問題の答えを \(1\) 行に出力してください。
あなたが KowerKoint 君に勝てる場合、最初の操作で選ぶべき長方形領域を、長方形領域 \((r_1,c_1,r_2,c_2)\) としたとき、以下の形式で出力してください。
| \(r_1~c_1~r_2~c_2\) |
答えが複数ある場合、いずれを出力しても正答とみなされます。
以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。
13 4
1 1 1 2
31 42 21 5
-1 1 1 1 2 -1
22 43 5
-1 1 3 1 4
549 2371 5298 4655 10025 37
-1 1 39 1 49 -1 1 79 1 89 1 13 1 25
1つ目のサンプルは部分点1の制約を満たします。
2つ目のサンプルは部分点2の制約を満たします。
3つ目のサンプルにおいて、ゲームの初期状態は以下の画像のようになっています。
あなたは最初の操作で \(1\) 番目のグリッド を選んで勝つことはできませんが、\(2\) 番目のグリッドを選ぶ場合、例えば以下の画像のように塗りつぶせば、以降両者が最適に操作を行うときあなたが勝ちます。