AT_tkppc2015_f 吹奏楽部 (Brass Band)

[problemUrl]: https://atcoder.jp/contests/tkppc/tasks/tkppc2015_f joisinoお姉ちゃんは次は吹奏楽部に行ってみようと思った。 joisinoお姉ちゃんが興味をもって音楽室に行くと、そこで顧問の先生が困っていた。 joisinoお姉ちゃんは優秀なプログラマーであることを見込まれて、先生から相談を受けた。 相談の内容は以下のとおりである。 3. この吹奏楽部では$ N $個の楽器が使用されており、それぞれに$ 1～N $までの番号が割り振られている。楽器$ i(1≦i≦N) $の奏者は$ i $人いる。 4. 楽器$ i $を美しく響かせるため、それを使う$ i $人は、舞台を横に$ i+1 $等分した位置に均等に並ぶ必要がある。このようにして、$ N $個の楽器を使う全員が舞台上に横一列に並ぶ。 5. 人の幅は考えないものとするが、二人以上の人が全く同じ位置に立った場合、そのうち最も番号の小さい楽器を使う人だけがその位置に立ち、他の楽器を使う人は舞台に立つことはできない。 6. この吹奏楽コンテストには$ M $人の審査員がおり、それぞれに$ 1～M $までの番号が割り振られている。彼らは舞台と平行に並んでいる。 7. 審査員$ j(1≦j≦M) $は、舞台の横の長さを$ 1 $とした時、舞台の左端から、$ P_j/Q_j $ の位置にいる。 8. 審査員にはそれぞれ決まった距離がある。審査員$ j $は自分との距離が決まった距離以内にいる奏者を見ることになっており、その人数は$ K_j $だとわかっている。 9. 練習の参考とするために、それぞれの審査員が見ている人の中で、最もその審査員から遠いところにいる人が演奏している楽器の番号が知りたい。 優秀なプログラマーであるjoisinoお姉ちゃんは、現在分かっている情報(楽器の個数$ N $、審査員の人数$ M $、審査員$ j $の位置$ P_j/Q_j $、見ている奏者の人数$ K_j $)をもとに、審査員$ j $が見る奏者の中で最も遠い人が演奏する楽器の番号を求めるプログラムを作成することにした。 なお、最も遠い距離にいる奏者が二人の場合、そのうち片方だけが見られるということはあり得ない。また、その二人のうち演奏する楽器の番号が小さいほうを出力せよ。（同じ場合はそのまま出力せよ）

入力は以下の形式で標準入力から与えられる。 . > $ N $ $ M $ $ P_1 $ $ Q_1 $ $ K_1 $ $ P_2 $ $ Q_2 $ $ K_2 $ : $ P_M $ $ Q_M $ $ K_M $ - $ 1 $行目には、楽器の個数$ N(1≦N≦3*10^4) $、審査員の数$ M(1≦M≦30) $が空白区切りで書かれている。 - $ 2 $行目からの$ M $行のうち$ j $行目には、審査員$ j $の位置を表す整数$ P_j(1≦P_j＜Q_j) $ $ Q_j(2≦Q_j≦N+1) $ 見る奏者の人数$ K_j $が空白区切りで書かれている。 - すべての入力において、審査員の見る人数が、奏者全員の人数を超えることはない。

出力は$ M $行からなる。$ j $行目には、審査員$ j $が見る中で最も遠い奏者が演奏している楽器の番号を出力せよ。 また、出力の末尾には改行を入れること。

### 配点 この問題には部分点が設定されている。 3. データセット$ 1 $では、$ N≦5000 $を満たし、正解すると$ 15 $点が得られる 4. データセット$ 2 $には追加の制約はなく、正解すると$ 105 $点が得られる ### Sample Explanation 1 \- この場合、舞台上には下図のように奏者が並んでいる。（青い線が舞台の端を表し、数字はその番号の楽器を持った奏者がそこにいることを表す） 審査員$ 1 $は緑の矢印の位置から、緑の括弧の範囲にいる$ 3 $人を見ている。括弧内の中で最も遠い奏者は$ 1 $の奏者なので、$ 1 $を出力する。 審査員$ 2 $は赤の矢印の位置から、赤の括弧の範囲にいる$ 4 $人を見ている。括弧内の中で最も遠い奏者は$ 2 $の奏者と$ 5 $の奏者なので、番号の小さい$ 2 $を出力する。 ### Sample Explanation 2 \- この場合、審査員$ 4 $の見る範囲が舞台の端を超えている。