AT_joisc2020_b 美味しい美味しいハンバーグ (Hamburg Steak)

あなたは Just Odd Inventions 社を知っているだろうか？　この会社の業務は「ただ奇妙な発明(just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ． 今はJOI社の新年会で，広大な金網の上でN枚のハンバーグを焼いている．ここでは金網は縦と横が共に $1000000000$マスの2次元のマス目として扱う．左からx番目，下からy番目のマス($1\le x\le1000000000$，$1\le y\le 1000000000$) を $(x,y)$ と表すことにする． ハンバーグには1からNまでの番号が付いており，ハンバーグ $i(1\le i\le N)$ は，マス $(L_i,D_i)$を左下，マス $(R_i,U_i)$ を右上とする長方形領域にある．なお，ハンバーグ同士が重なっていることもあり得る． JOI 社の新入社員であるあなたの仕事は，鉄板上のK個のマスを選び，それらのマスの中心に竹串を金網と垂直に刺すことによって，すべてのハンバーグの焼き加減を確認することである．各ハンバーグの焼き加減は，その上の $1$ 個以上のマスに竹串を刺すことで確認することができる．同じマスに複数の竹串を刺してもよいし，ハンバーグのないマスに竹串を刺してもよい． すなわち，あなたの仕事は以下の条件を満たす，相異なるとは限らないK個の整数対 $(x_1,y_1),\dots,(x_K,y_K)$を，$1$ 組探すことである： - すべての $i$ $(1\le i\le N)$について，$L_i \le x_j \le R_i$ かつ $D_i \le y_j \le U_i$ を満たす $j$($1\le j\le K$) が存在する． - すべての $j$($1\le j\le K$)について，$1\le x_j \le 1000000000$ かつ $1\le y_j \le 1000000000$ である． ハンバーグの位置と竹串の本数が与えられたとき，竹串の刺し方を $1$ つ求めるプログラムを作成せよ．ただしこの問題では，上の条件を満たすマスの組が存在するような入力のみが与えられる．

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である． > $N\ K$ > > $L_1\ D_1\ R_1\ U_1$ > > $L_2\ D_2\ R_2\ U_2$ > > $L_N\ D_N\ R_N\ U_N$

標準出力に $K$ 行で出力せよ．$j$ 行目 ($1\le j\le K$) 行目には，$x_j,y_j$ を空白区切りで出力せよ． 条件を満たす竹串の刺し方が複数存在する場合は，どれを出力してもよい．

制約 - $1\le N \le200000$． - $1\le K\le4$． - $1\le L_i \le R_i \le1000000000(1 \le i \le N)$． - $1\le D_i \le U_i \le1000000000(1 \le i \le N)$． - 問題文の条件を満たす $K$ 個のマスの組が存在する． 小課題 1. ($1$ 点) $N \le 2000，K = 1$． 2. ($1$ 点) $N \le 2000，K = 2$． 3. ($3$ 点) $N \le 2000，K = 3$． 4. ($6$ 点) $N \le 2000，K = 4$． 5. ($1$ 点) $K = 1$． 6. ($3$ 点) $K = 2$． 7. ($6$ 点) $K = 3$． 8. ($79$ 点) $K = 4$． マス $(2,2)$ に竹串を刺すことでハンバーグ $1,2$ の焼き加減を確認することができ，マス $(7,4)$ に竹串を刺すことでハンバーグ $3,4$ の焼き加減を確認することができる．$(2, 2)$ と $(7,4)$ 以外にも，$(3,3)$ と $(6,4)$ なども条件を満たす．