F - 吹奏楽部 (Brass Band) 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

問題文

joisinoお姉ちゃんは次は吹奏楽部に行ってみようと思った。
joisinoお姉ちゃんが興味をもって音楽室に行くと、そこで顧問の先生が困っていた。
joisinoお姉ちゃんは優秀なプログラマーであることを見込まれて、先生から相談を受けた。

相談の内容は以下のとおりである。

  • この吹奏楽部ではN個の楽器が使用されており、それぞれに1～Nまでの番号が割り振られている。楽器i(1≦i≦N)の奏者はi人いる。
  • 楽器iを美しく響かせるため、それを使うi人は、舞台を横にi+1等分した位置に均等に並ぶ必要がある。このようにして、N個の楽器を使う全員が舞台上に横一列に並ぶ。
  • 人の幅は考えないものとするが、二人以上の人が全く同じ位置に立った場合、そのうち最も番号の小さい楽器を使う人だけがその位置に立ち、他の楽器を使う人は舞台に立つことはできない。
  • この吹奏楽コンテストにはM人の審査員がおり、それぞれに1～Mまでの番号が割り振られている。彼らは舞台と平行に並んでいる。
  • 審査員j(1≦j≦M)は、舞台の横の長さを1とした時、舞台の左端から、P_j/Q_j の位置にいる。
  • 審査員にはそれぞれ決まった距離がある。審査員jは自分との距離が決まった距離以内にいる奏者を見ることになっており、その人数はK_jだとわかっている。
  • 練習の参考とするために、それぞれの審査員が見ている人の中で、最もその審査員から遠いところにいる人が演奏している楽器の番号が知りたい。

    • 優秀なプログラマーである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が空白区切りで書かれている。
    • すべての入力において、審査員の見る人数が、奏者全員の人数を超えることはない。

    配点

    この問題には部分点が設定されている。

  • データセット1では、N≦5000を満たし、正解すると15点が得られる
  • データセット2には追加の制約はなく、正解すると105点が得られる

    • 出力

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

    入力例1

    5 2
3 5 3
1 4 4

    出力例1

    1
2
    • この場合、舞台上には下図のように奏者が並んでいる。（青い線が舞台の端を表し、数字はその番号の楽器を持った奏者がそこにいることを表す）
      審査員1は緑の矢印の位置から、緑の括弧の範囲にいる3人を見ている。括弧内の中で最も遠い奏者は1の奏者なので、1を出力する。
      審査員2は赤の矢印の位置から、赤の括弧の範囲にいる4人を見ている。括弧内の中で最も遠い奏者は2の奏者と5の奏者なので、番号の小さい2を出力する。

    入力例2

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

    出力例2

    1
5
7
4
6
    • この場合、審査員4の見る範囲が舞台の端を超えている。