F - Greedy Takahashi Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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 にはどの都市にいるか、あるいはどのバスに乗っているか。

制約

  • 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)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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 にいずれかの都市にいるならば、その都市の番号を出力する。

入力例 1

3 2 3
1 2 1 3
2 3 3 5
1 1 5
2 2 3
1 3 2

出力例 1

2 3
2
3

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 を空白区切りで出力します。

入力例 2

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

出力例 2

4
6 1
4 1
8
6 1
1
2
2
7 2
1

Score : 500 points

Problem Statement

There are N cities numbered 1 through N, and M buses that go between these cities. The i-th bus (1 \leq i \leq M) departs from City A_i at time S_i+0.5 and arrive at City B_i at time T_i+0.5.

Takahashi will travel between these N cities. When he is in City p at time t, he will do the following.

  1. If there is a bus that departs from City p not earlier than time t, take the bus that departs the earliest among those buses to get to another city.
  2. If there is no such bus, do nothing and stay in City p.

Takahashi repeats doing the above until there is no bus to take. It is guaranteed that all M buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible.

Here is your task: process Q queries, the i-th (1 \leq i \leq Q) of which is as follows.

  • If Takahashi begins his travel in City Y_i at time X_i, in which city or on which bus will he be at time Z_i?

Constraints

  • 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)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line should contain the response to the i-th query as follows.

  • If Takashi is on some bus at time Z_i, print two integers representing the city from which the bus departs and the city at which the bus arrives, in this order, with a space between them.
  • Otherwise, that is, if Takahashi is in some city at time Z_i, print an integer representing that city.

Sample Input 1

3 2 3
1 2 1 3
2 3 3 5
1 1 5
2 2 3
1 3 2

Sample Output 1

2 3
2
3

In the first query, Takahashi will travel as follows.

  1. Start in City 1 at time 1.
  2. Take the bus that departs from City 1 at time 1.5 and arrives at City 2 at time 3.5.
  3. Take the bus that departs from City 2 at time 3.5 and arrives at City 3 at time 5.5.
  4. Since no bus departs from City 3 at time 5.5 or later, stay in City 3 (forever).

At time 5, he will be on the bus that departs from City 2 and arrives at City 3. Thus, as specified in the Output section, we should print 2 and 3 with a space between them.

Sample Input 2

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

Sample Output 2

4
6 1
4 1
8
6 1
1
2
2
7 2
1