Có N người xếp hàng chờ xử lý tại một quầy dịch vụ. Người thứ i đến tại thời điểm \(t_i\) và cần \(p_i\) đơn vị thời gian để xử lý. Quầy chỉ xử lý một người tại một thời điểm theo nguyên tắc FIFO (First-In-First-Out).

Hãy mô phỏng quá trình và tính thời điểm hoàn thành cho mỗi người.

Đầu vào

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 1000).
• N dòng tiếp theo, mỗi dòng chứa hai số nguyên \(t_i\) và p_i (0 ≤ t_i ≤ \(10^3\), 1 ≤ p_i ≤ \(10^3\)).

Đầu ra

In ra N số nguyên là thời điểm hoàn thành của người thứ i (theo thứ tự xử lý, không phải thứ tự đến).

Ví dụ

Input:
3
0 5
2 3
4 2

Output:
5 8 10

Ràng buộc & Subtasks