\(S_i,T_i\) を「時刻表上の発車・到着時刻」、\(S_i+X_i,T_i+X_i\) を「実際の発車・到着時刻」と呼ぶことにします。

電車の発車を遅らせても他の電車の発車を早めることはできないため、全ての電車は発車可能な最も早い時刻に発車するとしてよいです。

ある電車 \(i\) が発車可能かどうかに影響するのは、時刻表上の到着時刻が電車 \(i\) の時刻表上の発車時刻より前の電車に限ります。よって、時刻表上の発車・到着時刻の順に電車を処理することでうまくいきそうです。

実際、\(2M\) 個の発車・到着イベントを時刻表上の発車・到着時刻の順に ソートしたあと、順に次のような処理を行うことで処理できます。

• 電車 \(i\) が発車する際には、現在までに処理した電車（すなわち時刻表上の到着時刻が電車 \(i\) の時刻表上の発車時刻までの電車）の駅 \(A_i\) への実際の到着時刻に基づいて \(X_i\) を計算する
• 電車 \(i\) が到着する際には、\(X_i\) に基づいて、駅 \(B_i\) に実際に到着した到着時刻を記録する

これらの処理は、各駅 について「現在までに到着処理を行った電車のうち、もっとも遅い実際の到着時刻」を管理することで、どちらも \(O(1)\) で行うことができます。

発車と到着が同じ時刻に起こる際は、到着の処理を先に行う必要があることに注意してください。

writer解(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:
    # 出発　駅A[i]に来るのが最も遅い電車に合わせて発車する（電車1以外）
    if i:
      ans[i]=max(0,station[A[i]]-t)
  else:
    # 到着　駅B[i]に着いた最も遅い電車の情報を更新する
    station[B[i]]=max(station[B[i]],t+ans[i])

print(*ans[1:])