CSES - Maantiekiitäjä
  • Time limit: 4.00 s
  • Memory limit: 128 MB
Uolevi katsoo laadukasta piirrossarjaa, jossa Maantiekiitäjä juoksee suoralla tiellä, jolle Kelju K. Kojootti on asettanut kiviä esteiksi. Sarjan vanhana fanina Uolevi tietää, että Kojootti ei koskaan saa Maantiekiitäjää kiinni. Uolevi haluaa analysoida Maantiekiitäjän reittiä tarkemmin.

Maantiekiitäjä aloittaa kohdasta $0$ ja kiitää aina eteenpäin, kunnes törmää kiveen. Jokaiseen kiveen liittyy kaksi siirtymää: paljonko Maantiekiitäjä siirtyy törmäyksen jälkeen ja paljonko kivi siirtyy. Jos Maantiekiitäjä tai kivi päätyy törmäyksen jälkeen toisen kiven päälle, tämä kivi katoaa.

Tie kulkee ympäri maapallon ja on pituudeltaan $10^9$. Sen kohdat ovat kokonaisluvut $0,1,\ldots,10^9-1$. Kohdan $10^9-1$ jälkeen tulee taas $0$ ja kohtaa $0$ ennen tulee $10^9-1$. Jos tietä kulkee $10^9$ askelta eteenpäin, päätyy takaisin samaan kohtaan.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $t$: kivien määrä ja törmäysten määrä. Kivet on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on $n$ riviä, joista jokainen sisältää kolme kokonaislukua $x_k$, $a_k$ ja $b_k$: kiven $k$ sijainti sekä Maantiekiitäjän ja kiven siirtymät törmäyksen jälkeen. Jokainen kivi on eri kohdassa ja mikään kivi ei ole kohdassa $0$. Lisäksi törmäyksen jälkeen Maantiekiitäjä ja kivi eivät koskaan päädy samaan paikkaan.

Tuloste

Ohjelmasi tulee tulostaa $t$ ensimmäistä kiveä, joihin Maantiekiitäjä törmää.

Rajat
  • $1 \le n \le 5\cdot10^4$
  • $1 \le t \le 5\cdot10^4$
  • $0 < x_k < 10^9$
  • $-10^9 \le a_k \le 10^9$
  • $-10^9 \le b_k \le 10^9$
Esimerkki

Syöte:
3 5
100 300 -500
400 -200 -300
500 100 200


Tuloste:
1
3
3
3
3