列车延误

题目描述

在 AtCoder 国有 $N$ 个城市，编号为 $1$ 到 $N$，有 $M$ 列列车，编号为 $1$ 到 $M$。 列车 $i$ 在时刻 $S_i$ 从城市 $A_i$ 出发，在时刻 $T_i$ 到达城市 $B_i$。

给定正整数 $X_1$，求非负整数 $X_2,\ldots,X_M$ 的取值，使其满足以下条件，且使 $X_2+\ldots+X_M$ 最小。

条件：对于所有满足 $1 \leq i,j \leq M$ 的数对 $(i,j)$，若 $B_i=A_j$ 且 $T_i \leq S_j$，则 $T_i+X_i \leq S_j+X_j$。

也就是说，对于任何原本可以换乘的列车对，即使将每列列车 $i$ 的出发和到达时刻分别推迟 $X_i$，仍然可以换乘。

可以证明，使 $X_2+\ldots+X_M$ 最小的 $X_2,\ldots,X_M$ 的取法是唯一的。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $X_1$
$A_1$ $B_1$ $S_1$ $T_1$
$\vdots$
$A_M$ $B_M$ $S_M$ $T_M$

输出格式

输出满足条件且总和最小的 $X_2,\ldots,X_M$，按顺序以空格分隔。

样例

3 6 15
1 2 10 20
1 2 20 30
2 3 25 40
2 3 35 50
3 1 15 30
3 1 45 60

0 10 0 0 5

列车 1 从城市 1 到 2 的到达时刻推迟 15，变为时刻 35。

为了能在城市 2 从列车 1 换乘到列车 3，列车 3 的出发时刻推迟 10，变为时刻 35 出发、时刻 50 到达。

进一步，为了能在城市 3 从列车 3 换乘到列车 6，列车 6 的出发时刻推迟 5，变为时刻 50 出发。

其他列车可以在不延误的情况下运行，同时仍能保证原本可以换乘的列车对之间可以换乘，因此 $(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5)$ 满足条件。

而且不存在满足条件且总和更小的解，因此这就是答案。

10 9 100
1 10 0 1
10 2 1 100
10 3 1 100
10 4 1 100
10 5 1 100
10 6 1 100
10 7 1 100
10 8 1 100
10 9 1 100

100 100 100 100 100 100 100 100

4 4 10
1 2 0 1
1 2 0 10
2 3 100 200
2 4 100 200

0 0 0

数据范围

• $2 \le N \le 2\times 10^5$
• $2 \le M \le 2\times 10^5$
• $1 \le A_i,B_i \le N$
• $A_i \neq B_i$
• $0 \le S_i \lt T_i \le 10^9$
• $1 \le X_1 \le 10^9$
• 所有输入值均为整数。