F. Flying Pig Borrowing Log
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A certain high school requires students to read several selected books. Among those books, there is one outstanding book titled "Flying Pig".

There are $$$N$$$ students, numbered from $$$1$$$ to $$$N$$$, who are planning to read this book. There are $$$M$$$ days in a semester. The library opens every day for the entire semester, and the book is available from the beginning of the semester. The $$$i$$$-th student will visit the library the first time on day $$$b_i$$$ and will visit again on day $$$b_i + a_i, b_i + 2 \cdot a_i,\dots,b_i + x \cdot a_i$$$ where $$$1 \leq x$$$ and $$$b_i + x \cdot a_i \leq M$$$.

On day $$$d$$$, if a student visits the library and the book is available and the student has not read it before, the student borrows it and returns it exactly $$$c_i$$$ days later; that is, if the $$$i$$$-th student borrows the book on day $$$d$$$, it becomes available again on day $$$d + c_i$$$. If multiple students visit on the same day, the book is given to the student with the smallest number. A student may also borrow the book even if $$$d + c_i \gt M$$$, in which case the return is considered to happen after the $$$M$$$-th day.

For each student, print the day the student gets to borrow the book, or $$$-1$$$ if the student will not be able to borrow the book until the end of the semester.

Input

The first line contains two integers, $$$N$$$ and $$$M$$$ — the number of students and the number of days in the semester. $$$(1 \leq N, M \leq 100,000)$$$

The next $$$N$$$ lines contain three integers, $$$a_i, b_i,$$$ and $$$c_i$$$ — the numbers for the $$$i$$$-th student visitation pattern stated in the problem statement, and the duration of the $$$i$$$-th student borrowing. $$$(1 \leq a_i, b_i, c_i \leq M)$$$.

Output

Output one line with $$$N$$$ integers – the day student $$$1,2,3,\dots,N$$$ gets to borrow the book, or $$$-1$$$ if the student will not be able to borrow the book until the end of the semester.

Example
Input
3 10
4 2 3
3 4 1
5 2 1
Output
2 7 -1
Note

Sample Explanation

Student $$$1$$$ visited the library on days $$$2$$$, $$$6$$$, and $$$10$$$.

Student $$$2$$$ visited the library on days $$$4$$$, $$$7$$$, and $$$10$$$.

Student $$$3$$$ visited the library on days $$$2$$$ and $$$7$$$.

On day $$$2$$$, students $$$1$$$ and $$$3$$$ visited the library, but student $$$1$$$ had a lower number, so the book was borrowed by student $$$1$$$.

On day $$$4$$$, student $$$2$$$ visited, but the book was not available.

On day $$$5$$$, student $$$1$$$ returned the book. The book became available again, but it was not borrowed since no one visited the library that day.

On day $$$7$$$, students $$$2$$$ and $$$3$$$ visited the library, but student $$$2$$$ had a lower number, so the book was borrowed by student $$$2$$$.

On day $$$8$$$, student $$$2$$$ returned the book. The book became available again, but it was not borrowed since no one visited the library that day.

On day $$$10$$$, students $$$1$$$ and $$$2$$$ visited the library, but both of them had already read the book, so it was not borrowed.