Problem Description

In the country of Atcoder, there are $N$ towns numbered from $1$ to $N$ and $M$ trains running, numbered from $1$ to $M$.
Train $i$ departs from town $A_i$ at time $S_i$ and arrives at town $B_i$ at time $T_i$.

Given a positive integer $X_1$, determine $0$ or more integers $X_2, \ldots, X_M$ such that the sum $X_2 + \ldots + X_M$ is minimized while satisfying the following conditions:

• For all pairs $(i, j)$ where $1 \leq i, j \leq M$, if $B_i = A_j$ and $T_i \leq S_j$, then $T_i + X_i \leq S_j + X_j$.
• This means that the originally transferable pairs of trains remain transferable even if the departure and arrival times of each train $i$ are delayed by $X_i$.

It can be proven that there is a unique way to determine $X_2, \ldots, X_M$ that minimizes the sum $X_2 + \ldots + X_M$.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the $X_2, \ldots, X_M$ that satisfy the conditions and minimize the sum, separated by spaces in this order.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0 10 0 0 5

Sample Input #2

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

Sample Output #2

100 100 100 100 100 100 100 100

Sample Input #3

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

Sample Output #3

0 0 0

Notes/Hints

Constraints

• $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 < T_i \leq 10^9$
• $1 \leq X_1 \leq 10^9$
• All inputs are integers

Sample Explanation 1

The arrival of train 1 going from town 1 to town 2 is delayed by 15, making it arrive at time 35. To transfer from train 1 to train 3 at town 2, the departure time of train 3 is delayed by 10, making it depart at time 35 and arrive at time 50. Furthermore, to transfer from train 3 to train 6 at town 3, the departure time of train 6 is delayed by 5, making it depart at time 50. Other trains do not need to be delayed, and the originally transferable trains can still transfer, so $(X_2, X_3, X_4, X_5, X_6) = (0, 10, 0, 0, 5)$ satisfies the conditions. Since there is no other way to satisfy the conditions with a smaller sum, this is the answer.

见题面 Input 部分

见题面 Output 部分