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