問題文
在高桥王国 有 N 个城市,每个城市都有 以 1 ~ N 整数编号。
在高桥王国 有 K 不同的民族居住在那里,i 第二个民族是城市。 我住在 S_i 。
高桥王国的族群有一种名为“民族大迁徙”的文化,他们每100年更换一次居住的城市。 基本上各民族同时进行“民族大迁徙”,但如果各民族在同一天迁徙,预计会出现拥堵,因此每天设置以下迁徙限制。 D 需要一天的时间。
- i 当天城市号码为 L_i 以上 R_i 您可以按如下方式在城镇之间自由移动。禁止所有其他活动。
每个民族都遵守这些行动限制,并通过多个城市前往目的地城市。
i 第th族的目的地是城市。 T_i 。各族人民都希望尽快到达目的地。
查找每个种族的最早可能到达日期。
此外,任何种族群体 保证在 D 天内到达您的目的地。
入力
输入将以以下形式从标准输入给出。
N D K L_1 R_1 L_2 R_2 : L_D R_D S_1 T_1 S_2 T_2 : S_K T_K
- 1 行中显示了高桥王国的城镇数量。 N(1 ≦ N ≦ 10^9) ,大迁徙花费的天数 D(1 ≦ D ≦ 10^4) ,居住在高桥王国的族群数量 来自行 K(1 ≦ K ≦ 100) 用空格分隔。
- 2 从线 D 行数过多 i 在线 i 表示当天的行动限制。 2 整数 L_i, R_i(1 ≦ L_i ≦ R_i ≦ N) 用空格分隔。
- D+2 从线 K 行数过多 i 在线 i 第th民族原来居住的城市 S_i( 1 ≦ S_i ≦ N),目的地城市 T_i (1 ≦ T_i ≦ N) 用空格分隔。此时 S_i ≠ T_i 成立。
- 任何种族 保证您在 D 天内到达目的地。
出力
输出是 由 K 行组成。 打印第 i 在线 i 个族裔群体可以到达目的地的第一天。 还在输出末尾添加换行符。 第
入力例1
10 10 3 1 5 3 6 7 10 5 8 4 4 1 4 2 9 1 3 1 1 4 5 1 6 2 7 10 1
出力例1
2 4 8
1 个族群可以按如下方式移动: 您可以在 2 天后到达目的地。你不能移动得比这更快。
- 1 当天所在城市 1 从城市出发 转至 4 。
- 2 当天所在城市 4 从城市出发 转至 6 。
2 个族群可以按如下方式移动: 您可以在 4 天后到达目的地。你不能移动得比这更快。
- 1 当天所在城市 2 从城市出发 转至 5 。
- 4 当天所在城市 5 从城市出发 转至 7 。
3 个族群可以按如下方式移动: 您可以在 8 天后到达目的地。你不能移动得比这更快。
- 3 当天所在城市 10 从城市出发 转至 9 。
- 7 当天所在城市 9 从城市出发 转至 3 。
- 8 当天所在城市 3 从城市出发 转至 1 。
入力例2
10 10 4 1 2 2 4 3 6 4 8 5 10 9 10 7 8 5 6 3 5 1 3 10 1 3 8 2 4 1 3
出力例2
10 4 2 2
入力例3
314159265 10 1 1 10000 500 12031 1414 113232 111111 777777 666661 23423423 12345678 123456789 111111111 314159265 112334 235235235 1 223445 314 1592 1 314159265
出力例3
7