AT_abc212_f [ABC212F] Greedy Takahashi

### 题目大意 有 $n$ 座城市和 $m$ 辆公交车，第 $i$ 辆公交车会在 $S_i+0.5$ 时从城市 $A_i$ 出发，在 $T_i+0.5$ 时到达城市 $B_i$。 Takahashi 想要在这些城市中旅行。具体的说，当他在 $t$ 时刻时位于城市 $p$ 时，他会按照如下方案移动： 若存在在 $t$ 时刻后从城市 $p$ 出发的公交车，那么选择其中离 $t$ 时刻最近的一辆并乘坐。否则停留在城市 $p$ 不移动。 现在 Takahashi 想要问你 $Q$ 个问题，每个问题的格式如下： 如果 Takahashi 在 $X$ 时刻从城市 $Y$ 出发，那么 $Z$ 时刻时 Takahashi 位于哪辆公交车上或者哪个城市中？

第一行三个正整数 $n,m,Q$。 接下来 $m$ 行，每行四个正整数 $A_i,B_i,S_i,T_i$，描述一辆公交车。 接下来 $Q$ 行，每行三个正整数 $X,Y,Z$，描述一个询问。

输出共 $Q$ 行，每行一个或两个正整数。 如果是城市，输出城市编号，如果是公交车，输出其起点和终点的城市编号。 Translated by \_Ponder_

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