Vedúci zistili, že nemajú dostatok chutných lasagní pre všetkých a niektorí vedúci budú musieť jesť nie až tak oblúbenú dusenú zeleninu. Takmer okamžite sa strhla hádka o to, kto bude jesť lasagne, a kto nie. Aby sa vedúci o lasagne nepobili, tak sa dohodli, že si o ne spravia závod na elektrokolobežkách.

Závod sa uskutoční na parkovisku širokom $w$ metrov a dlhom $l$ metrov. Na tomto parkovisku je taktiež $n$ nabíjacích staníc pre kolobežky, ktoré pri prechode cez ne instantne nabijú kolobežku na $100$%. Keďže baterky sú ťažké, tak by každý vedúci rád vedel, akú najmenšiu baterku potrebuje, aby prešiel celú trasu. Pomôžte im to zistiť.

Úloha

Máme parkovisko široké $w$ metrov a dlhé $l$ metrov. Na tomto parkovisku sa nachádza $n$ nabíjacích staníc. Nabíjacia stanica je zvislý pruh, $i$-ta nabíjacia stanica sa nachádza v stĺpci $x_i$, na rozpätí riadkov $y_{0,i}$ až $y_{1,i}$. Ak kolobežka prejde cez nabíjaciu stanicu (počíta sa aj jej okraj), tak sa okamžite nabije na plnú kapacitu.

Máme $w+1$ možných štartovacích pozícií pre kolobežky, $y \in [0,w]$, a pre každú z nich by sme radi vedeli akú najmenšiu batériu potrebuje mať kolobežka závodiaca na danom riadku, aby zvládla prejsť celú trasu. Vieme, že za jednu jednotku nabitia prejde kolobežka jeden meter.

Formát vstupu

V prvom riadku vstupu sú čísla $n,w,l$ ($1 \leq n,w,l \leq 2\times 10^5$) udávajúce počet nabíjacích staníc, šírku a dĺžku parkoviska.

Na nasledujúcich $n$ riadkoch sa nachádzajú popisy nabíjacích staníc. Na $i$-tom riadku sú čísla $x_i, y_{0,i}, y_{1,i}$, ($0 < x_i < l, 0 \leq y_{0,i} < y_{1,i} \leq w$).

V jednotlivých sadách platia nasledujúce obmedzenia:

Je garantované, že sa nabíjacie stanice nepretínajú, a ani nedotýkajú.

Formát výstupu

Vypíš $w+1$ riadkov, na $i$-tom z nich vypíš minimálnu potrebnú kapacitu pre kolobežku na $i$-tom riadku.

Príklad

Input:

4 5 10
2 1 3
4 2 4
7 1 3
9 0 2

Output:

9
5
3
3
6
10