„Am măsurat interiorul. Aș vrea să mă opresc acum.” — Costel, șeful de la mentenanță, văzut ultima dată în fundul liftului

Dorel a reparat liftul de pe stația spațială Zbeng-9, iar acum cabina este o dimensiune de buzunar. Încap toți, inclusiv o lună mică. Tanti Geta vrea să știe când iese din lift fiecare navetist. În această problemă, fiecare navetist este numit persoană.

Cerință

Pentru fiecare persoană, aflați secunda la care iese din lift. Secundele se numără de la secunda $0$, nu de la momentul în care apare persoana.

Clădirea. Etajele sunt numerotate de la $1$ la $F$. Există un singur lift, în care încap oricâte persoane. La secunda $0$, liftul se află pe etajul $s$, este inactiv și are ușile închise.

Persoanele. Persoana $i$ apare la secunda $t_i$ pe etajul $a_i$ și vrea să ajungă pe etajul $b_i$. Ea vrea în sus dacă $b_i > a_i$ și în jos dacă $b_i < a_i$.

Cum funcționează liftul

Liftul se deplasează cu un etaj pe secundă. Continuă în direcția curentă cât timp este ceva în față: destinația unui pasager sau o persoană care așteaptă mai departe, indiferent în ce direcție vrea să meargă. Când nu mai este nimic în față, se întoarce. Dacă nici în acea direcție nu este nimic, rămâne inactiv până apare cineva.

Aceste detalii stabilesc răspunsurile exacte:

• Intrarea în lift. O persoană care așteaptă intră când liftul este pe etajul ei și merge în direcția dorită de ea. Dacă liftul se întoarce pe acel etaj, persoanele care vor în noua direcție intră imediat.
• Plecarea din starea inactivă. Un lift inactiv merge în sus dacă cineva de pe etajul lui vrea în sus; altfel, în jos dacă cineva de pe etajul lui vrea în jos. În caz contrar, se îndreaptă spre cea mai apropiată persoană care așteaptă, iar la egalitate merge în sus.
• Ușile. Ușile se deschid când cineva iese sau intră în timp ce ele sunt închise. Dacă acest lucru se întâmplă la secunda $T$, ușile sunt deschise până la secunda $T + d$ inclusiv, iar liftul se poate deplasa din nou la secunda $T + d + 1$. Dacă cineva intră în timp ce ușile sunt deschise, acestea nu rămân deschise mai mult.
• Ordinea dintr-o secundă. Mai întâi liftul se deplasează, apoi pasagerii ies, apoi apar persoanele noi, apoi persoanele intră în lift și liftul își stabilește direcția. O persoană care apare pe etajul liftului poate intra în aceeași secundă.

Date de intrare

Pe prima linie a fișierului de intrare pd.in se găsesc patru numere întregi: $F$, $s$, $d$ și $n$. Aici, $F$ este numărul de etaje, $s$ este etajul de pornire, $d$ este timpul ușilor, iar $n$ este numărul de persoane.

Pe fiecare dintre următoarele $n$ linii se găsesc trei numere întregi: $t_i$, $a_i$ și $b_i$, pentru persoana $i$. Persoanele sunt numerotate de la $1$ la $n$ în ordinea din fișier și sunt date în ordine nedescrescătoare a valorilor $t_i$.

Date de ieșire

Fișierul de ieșire pd.out va conține $n$ linii. Pe linia $i$ se va găsi un număr întreg: secunda la care persoana $i$ iese din lift.

Restricții și precizări

• $2 \leq F \leq 10^9$
• $1 \leq s \leq F$
• $0 \leq d \leq 10^9$
• $1 \leq n \leq 2 \cdot 10^5$
• $0 \leq t_i \leq 10^9$
• $1 \leq a_i, b_i \leq F$ și $a_i \neq b_i$
• Răspunsurile pot necesita numere întregi pe $64$ de biți.
• Mai multe persoane pot ieși din lift în aceeași secundă.
• Datele de intrare conțin toate valorile $b_i$, dar liftul nu folosește destinația unei persoane care așteaptă. Folosește doar direcția în care vrea să meargă aceasta.

Exemplu

pd.in

10 1 1 5
0 3 8
0 3 5
0 5 1
1 6 2
2 2 9

pd.out

9
5
20
18
30

Explicație

Aici $d = 1$, deci ușile deschise la secunda $T$ sunt deschise la secundele $T$ și $T + 1$. Tabelul arată secundele importante: