Steve có đường truyền Internet tốc độ tối đa ~v~ MB/giây và viết một chương trình tải file theo cơ chế RR (Round Robin) như sau:

• Mỗi khi có một yêu cầu tải file xuất hiện, file đó được bắt đầu tải ngay lập tức.
• Tại mọi thời điểm, nếu đang có ~k~ file cùng được tải song song thì mỗi file nhận tốc độ ~v/k~ MB/giây.
• Khi một file tải xong tại một thời điểm nào đó (có thể nằm giữa các giây nguyên), hệ thống kết thúc ngay file đó và ngay lập tức chia lại băng thông cho các file còn lại (mọi thay đổi diễn ra tức thời trong cùng thời điểm đang xét).

Steve kích hoạt chương trình để tải ~n~ file. File thứ ~i~ bắt đầu tải tại thời điểm ~s_i~ và có dung lượng ~w_i~ MB. Dữ liệu đảm bảo ~s_i \le s_{i+1}~ với mọi ~i~.

Yêu cầu

Hãy xác định thời điểm hoàn tất tải của từng file theo đúng cơ chế trên, và in ra theo thứ tự từ file ~1~ đến file ~n~.

Dữ liệu

• Dòng đầu chứa 2 số nguyên ~n~ và ~v~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~s_i~ và ~w_i~.

Kết quả

In ra ~n~ số thực, mỗi số trên một dòng. Số thứ ~i~ là thời điểm hoàn tất tải của file thứ ~i~. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ~10^{-6}~.

Ví dụ

Ví dụ 1

Input

2 1
1 2
2 2

Output

4
5

Giải thích

Ví dụ 1

• Từ thời điểm ~1~ đến ~2~ chỉ có file 1, tốc độ ~1~ MB/giây ⇒ tải được ~1~ MB, còn ~1~ MB.
• Từ thời điểm ~2~ có 2 file cùng tải, mỗi file tốc độ ~1/2~ MB/giây. File 1 cần ~1~ MB ⇒ mất ~2~ giây, hoàn tất tại ~4~.
• Trong khoảng ~[2,4]~, file 2 tải được ~2 \cdot 1/2 = 1~ MB, còn ~1~ MB. Sau ~4~, chỉ còn file 2 nên tốc độ ~1~ MB/giây ⇒ xong tại ~5~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~1 \le v \le 10^9~
• ~1 \le s_i, w_i \le 10^9~
• ~s_i \le s_{i+1}~ với mọi ~1 \le i < n~