AT_abc212_f [ABC212F] Greedy Takahashi

[problemUrl]: https://atcoder.jp/contests/abc212/tasks/abc212_f $ 1 $ から $ N $ までの番号が振られた $ N $ 個の都市と、それらの間を運行する $ M $ 本のバスがあります。$ i\ (1\ \leq\ i\ \leq\ M) $ 本目のバスは時刻 $ S_i+0.5 $ に都市 $ A_i $ を出発し、時刻 $ T_i+0.5 $ に都市 $ B_i $ に到着します。 さて、これら $ N $ 個の都市の間を高橋くんが移動します。高橋くんは、時刻 $ t $ に都市 $ p $ にいるとき、以下のように行動します。 1. 時刻 $ t $ 以降（時刻 $ t $ ちょうどを含む）に都市 $ p $ を出発するバスが存在するなら、そのようなバスのうち最も出発時刻が早いものに乗り、他の都市に移動する。 2. そのようなバスが存在しないなら、何もせず都市 $ p $ に居続ける。 高橋くんは上記の行動を 2. の状態になるまで繰り返します。$ M $ 本のバスの出発時刻は互いに異なることが保証されるため、高橋くんが乗るバスは常に一意に定まります。また、バスの乗り換えにかかる時間は無視することができます。 それでは本題に入りましょう。$ Q $ 個のクエリに答えてください。$ i\ (1\ \leq\ i\ \leq\ Q) $ 個目のクエリの内容は以下の通りです。 - 高橋くんが時刻 $ X_i $ に都市 $ Y_i $ から行動を開始するとき、時刻 $ Z_i $ にはどの都市にいるか、あるいはどのバスに乗っているか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ A_1 $ $ B_1 $ $ S_1 $ $ T_1 $ $ A_2 $ $ B_2 $ $ S_2 $ $ T_2 $ $ \hspace{1.8cm}\vdots $ $ A_M $ $ B_M $ $ S_M $ $ T_M $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ \hspace{1.2cm}\vdots $ $ X_Q $ $ Y_Q $ $ Z_Q $

$ Q $ 行に渡って出力せよ。$ i $ 行目には、 $ i $ 個目のクエリに対する答えを以下の指示にしたがって出力すること。 - 高橋くんが時刻 $ Z_i $ にいずれかのバスに乗っているならば、そのバスの始点、終点となる都市の番号をこの順に空白区切りで出力する。 - そうでない、すなわち高橋くんが時刻 $ Z_i $ にいずれかの都市にいるならば、その都市の番号を出力する。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N\ (1\ \leq\ i\ \leq\ M) $ - $ A_i\ \neq\ B_i\ (1\ \leq\ i\ \leq\ M) $ - $ 1\ \leq\ S_i\ \lt\ T_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ M) $ - $ S_i\ \neq\ S_j\ (i\ \neq\ j) $ - $ 1\ \leq\ X_i\ \lt\ Z_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ Q) $ - $ 1\ \leq\ Y_i\ \leq\ N\ (1\ \leq\ i\ \leq\ Q) $ - 入力は全て整数 ### Sample Explanation 1 $ 1 $ つ目のクエリにおいて、高橋くんは以下の通りに動きます。 1. はじめ、都市 $ 1 $ に時刻 $ 1 $ にいる。 2. 時刻 $ 1.5 $ に都市 $ 1 $ を出発するバスに乗り、時刻 $ 3.5 $ に都市 $ 2 $ に到着する。 3. 時刻 $ 3.5 $ に都市 $ 2 $ を出発するバスに乗り、時刻 $ 5.5 $ に都市 $ 3 $ に到着する。 4. 時刻 $ 5.5 $ 以降に都市 $ 3 $ を出発するバスは存在しないため、都市 $ 3 $ に（永遠に）居続ける。 時刻 $ 5 $ において、高橋くんは都市 $ 2 $ を出発して都市 $ 3 $ に到着するバスに乗っています。そのため、「出力」の項に書かれている通り、$ 2 $, $ 3 $ を空白区切りで出力します。