24126번 - プラグ (Plugs) 다국어

JOI 国には電気プラグを作っている会社が N 社あり，JOI 国は各社に 1 から N までの整数を ID として 割り当てている．各電気プラグ会社は 1 組の電気プラグとソケットを作っているが，困ったことにすべて の会社の電気プラグおよびソケットは他社のそれらとは違った形状をしている．

JOI 国の法律でソケットには電気プラグ会社の ID を印字することになっているのだが，電気プラグには ID は印字されていない．とある電気店の店長は，そのような JOI 国の事情もあって，顧客の要求にすばや く対応できるように，JOI 国に存在する N 種類すべての電気プラグを１つずつ会社の ID 順に入れた道具箱 を持っていた．しかしある日，ふとした拍子に店長は道具箱の中身をバラバラにしてしまった．店長はあ る種のソケットにある種の電気プラグが入らないことは見抜けても，電気プラグを見てどの電気プラグ会 社の電気プラグかを判断することはできないため，道具箱の中身を元に戻すことができなくなってしまっ た．店長は困り果ててしまった末，どのような困難な問題でもいとも簡単に解いてしまうことで名高い L 教授に解決を依頼した．

L 教授は順番がばらばらになった電気プラグに整理のため 1 から N までの番号をふり，それを元に店長 から M 個の証言を引き出した．店長の k 個目の証言は「電気プラグ会社の ID が A_k から B_k のソケットに は，C_k 番目から D_k 番目のいずれの電気プラグも入らない」というものである．その後，L 教授は「謎は 解決した．この M 個の証言を満たす電気プラグと会社の対応関係は 1 つに決まった．あとは君にまかせた よ．」と言って帰ってしまった．非常に理不尽な話であるが，弟子であるあなたは問題を解決し電気プラグ と会社の対応関係を店長に知らせなければならない．

店長の証言から電気プラグの対応関係を特定するプログラムを作成せよ．

図 1

標準入力から以下の入力を読み込め．

• 1 行目には整数 N と M が空白を区切りとして書かれている．
• 続く M 行は，1 行につき 1 つの証言について記述している．これらの行のうちの k 行目は k 番目の 証言について記述しており，整数 A_k, B_k，C_k，D_k が空白を区切りとして書かれている．

標準出力に以下のデータを出力せよ．

• データは N 行からなり，i 行目は ID が i の会社が作っている電気プラグの番号を含む．

• 1 ≤ N ≤ 3, 000 JOI 国に存在する電気プラグ会社の数
• 1 ≤ M ≤ 100, 000 店長の証言の数
• 1 ≤ A_k ≤ B_k ≤ N, 1 ≤ C_k ≤ D_k ≤ N, 1 ≤ k ≤ M k 個目の証言の内容