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