Let us call \(S_i\) and \(T_i\) the scheduled departure and arrival, respectively, and \(S_i+X_i\) and \(T_i+X_i\) the actual departure and arrival.

If you let a train depart later, you cannot make another depart earlier, so we can assume that every train departs as early as possible.

Whether a train \(i\) can depart is only affected by the trains whose scheduled arrival is prior to the scheduled departure of train \(i\). Thus, processing trains in order of scheduled departure and arrival seems to work.

Indeed, one can sort the \(2M\) departure / arrival events in ascending order of their scheduled departure or arrival, and process them in order:

• When train \(i\) departs, find \(X_i\) based on the actual arrivals to station \(A_i\) of the trains processed so far (i.e. those whose scheduled arrivals are prior to the scheduled departure of train \(i\)).
• When train \(i\) arrives, record the actual arrival to station \(B_i\) based on \(X_i\).

These process can be both done in \(O(1)\) time by managing for each station the latest actual arrival of the trains that have been processed so far.

Note that if departure and arrival occurs at the same time, the arrivals must be processed first.

Writer’s solution (Python)

N,M,X=map(int,input().split())
A,B,S,T=zip(*[tuple(map(int,input().split())) for _ in range(M)])

event=sorted([(S[i],1,i) for i in range(M)] + [(T[i],0,i) for i in range(M)])

ans=[0]*M
ans[0]=X

station=[0]*(N+1)
for t,f,i in event:
  if f:
    # Departure: departs after the latest train arriving at station A[i] arrives (except for train 1)
    if i:
      ans[i]=max(0,station[A[i]]-t)
  else:
    # Arrival: update the latest train arriving at station B[i]
    station[B[i]]=max(station[B[i]],t+ans[i])

print(*ans[1:])