Максим, известный ученый-компьютерщик в области сетевых технологий, придумал новый протокол, который Рамазан предложил назвать cerr_maksim.

Для простоты предположим, что в сети есть два компьютера, соединенных проводом с пропускной способностью $w$. Файлы передаются с первого компьютера на второй. Передача файла размером $s$ занимает $\frac{s}{w}$ секунд.

Всего необходимо передать $n$ файлов, каждый из которых имеет момент времени $t_i$, когда он начинает передаваться, размер $s_i$ и приоритет $p_i$. Если одновременно передается несколько файлов, то пропускная способность провода распределяется между ними пропорционально их приоритетам.

Для каждого файла вычислите момент времени, когда он полностью поступит на второй компьютер.

Входные данные

Первая строка содержит два целых числа $n, w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^7$) — количество файлов и пропускная способность провода.

Каждая из следующих $n$ строк содержит три целых числа $t_i, s_i, p_i$ ($1 \le t_i \le 10^7$, $1 \le s_i \le 10^7$, $1 \le p_i \le 100$) — время начала передачи, размер и приоритет файла.

Выходные данные

Выведите $n$ вещественных чисел, где $i$-е число — это момент времени, когда завершится передача $i$-го файла.

Ваши ответы будут считаться верными, если для каждого из них абсолютная или относительная погрешность не превышает $10^{-6}$.

Примеры

Входные данные 1

2 10
0 100 2
4 200 1

Выходные данные 1

13
30

Входные данные 2

2 10
30 200 1
10 100 2

Выходные данные 2

50
20