Plugs(プラグ) - joi2010-day4

出典: 第9回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

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つに決まった. あとは君にまかせたよ.」と言って帰ってしまった. 非常に理不尽な話であるが, 弟子であるあなたは問題を解決し電気プラグと会社の対応関係を店長に知らせなければならない.

課題(TASK)

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

制限(CONSTRAINTS)

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個目の証言の内容

入力(INPUT)

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

• 1行目には整数NとMが空白を区切りとして書かれている.
• 続くM行は, 1行につき1つの証言について記述している. これらの行のうちのk行目はk番目の証言について記述しており, 整数A[k], B[k], C[k], D[k] が空白を区切りとして書かれている.

出力(OUTPUT)

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

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

採点基準(GRADING)

20点分のテストグループにおいてNおよびMは100を超えない.

入出力例(EXAMPLE)

入力例(Sample Input)	出力例(Sample Output)
3 2 1 1 2 3 1 2 3 3	1 2 3

上記の例は図1と一致する. 図1の点線は店長の証言により入らないことがわかっている組み合わせである.