네트워킹 분야의 저명한 컴퓨터 과학자인 Maksim은 Ramazan이 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