問題文

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 \leqq N \leqq 3{,}000：JOI 国に存在する電気プラグ会社の数．
• 1 \leqq M \leqq 100{,}000：店長の証言の数．
• 1 \leqq A_k \leqq B_k \leqq N，1 \leqq C_k \leqq D_k \leqq N，1 \leqq k \leqq M：k 個目の証言の内容．

採点基準

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

入力例 1

3 2
1 1 2 3
1 2 3 3

出力例 1

1
2
3

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

入力例 2

8 7
2 4 2 3
4 7 1 2
6 8 1 4
3 4 3 5
5 6 6 8
6 7 6 7
7 8 6 6

出力例 2

2
4
1
6
3
5
8
7