AT_abc368_e [ABC368E] Train Delay

Atcoder 国有 $1$ 到 $N$ 编号的 $N$ 个城市，以及 $1$ 到 $M$ 编号的 $M$ 列火车在运行。 第 $i$ 列火车会在时刻 $S_i$ 从城市 $A_i$ 出发，并在时刻 $T_i$ 到达城市 $B_i$。 给定正整数 $X_1$，请你确定 $0$ 以上的整数 $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$，按顺序用空格分隔。

## 限制 - $2\leq N\leq 2\times 10^5$ - $2\leq M\leq 2\times 10^5$ - $1\leq A_i,B_i\leq N$ - $A_i\neq B_i$ - $0\leq S_i