Xe điện của các pháp sư

Một thành phố có bến xe điện với $n$ chiếc xe. Mỗi ngày các xe lần lượt rời bến để tới trạm cuối, cách bến đúng $d$ mét.

Xe thứ $i$ rời bến tại thời điểm $t_i$ giây, chạy được với vận tốc không vượt quá $v_i$ mét/giây, và có thể tăng tốc với gia tốc không vượt quá $a$ mét/giây bình phương. Gia tốc tối đa $a$ là như nhau cho mọi xe. Xe có thể giảm tốc tức thời và thay đổi gia tốc tức thời tuỳ ý.

Các xe chạy chung một đường dây điện nên không thể vượt nhau. Nếu một xe đuổi kịp xe phía trước, hai xe sẽ đi sát nhau cho tới trạm cuối. Mọi tài xế đều lái sao cho tới trạm cuối sớm nhất có thể.

Khi rời bến, vận tốc của xe bằng $0$. Khi tới trạm cuối, vận tốc của xe không nhất thiết bằng $0$. Coi mỗi xe là một chất điểm, bỏ qua mọi ảnh hưởng tới vận tốc ngoài việc tăng tốc và giảm tốc của động cơ.

Với mỗi xe, hãy xác định thời điểm sớm nhất nó có thể tới trạm cuối.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $a$, $d$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $t_i$ và $v_i$.

Dữ liệu ra

In ra $n$ dòng, dòng thứ $i$ là thời điểm xe thứ $i$ tới trạm cuối, theo đúng thứ tự đã cho trong dữ liệu vào.

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a,d\le {10}^6$
• $0\le t_1<t_2<\dots <t_n\le {10}^6$
• $1\le v_i\le {10}^6$

Ví dụ