Maksim, một nhà khoa học máy tính nổi tiếng trong lĩnh vực mạng, đã nghĩ ra một giao thức mới mà Ramazan đề xuất đặt tên là cerr_maksim.

Để đơn giản, giả sử có hai máy tính trong mạng được kết nối với nhau bằng một đường truyền có băng thông $w$. Các tệp tin được truyền từ máy tính thứ nhất sang máy tính thứ hai. Việc truyền một tệp tin có kích thước $s$ mất $\frac{s}{w}$ giây.

Có $n$ tệp tin cần được truyền, mỗi tệp tin có thời điểm bắt đầu truyền $t_i$, kích thước $s_i$ và độ ưu tiên $p_i$. Nếu nhiều tệp tin được truyền đồng thời, băng thông của đường truyền sẽ được chia cho các tệp tin đó tỉ lệ thuận với độ ưu tiên của chúng.

Với mỗi tệp tin, hãy tính thời điểm mà nó truyền xong đến máy tính thứ hai.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n, w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^7$) — số lượng tệp tin và băng thông của đường truyền.

Mỗi dòng trong $n$ dòng tiếp theo chứa ba số nguyê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$) — thời điểm bắt đầu truyền, kích thước và độ ưu tiên của tệp tin.

Dữ liệu ra

In ra $n$ số thực, số thứ $i$ là thời điểm mà việc truyền tệp tin thứ $i$ hoàn tất.

Kết quả của bạn sẽ được coi là đúng nếu sai số tuyệt đối hoặc tương đối của mỗi số không vượt quá $10^{-6}$.

Ví dụ

Dữ liệu vào 1

2 10
0 100 2
4 200 1

Dữ liệu ra 1

13
30

Dữ liệu vào 2

2 10
30 200 1
10 100 2

Dữ liệu ra 2

50
20