CF589K Task processing

Vasya wants to create a computing system to process arbitrary tasks. As a part of the system he needs an algorithm which will choose an order of task execution. He came up with the following algorithm: - There is a single execution queue. For task to be completed, it needs to be added to the queue. - For each task two values are known: $ l_{i} $ and $ t_{i} $ — the number of seconds that it takes to complete the task and the moment of time when this task is added to the execution queue. - If at some moment of time $ T $ the algorithm has to select a task for execution, it picks the one with the minimum value of $ l_{i}-(T-t_{i})^{2} $ . In case of a tie, algorithm picks a task with the lowest index. Then for the following $ l_{i} $ seconds the algorithm will wait for the task to be completed. In order to test the algorithm Vasya wants you to simulate it. You are given $ n $ tasks. For each task, you know the number of seconds $ l_{i} $ that it takes to complete the task and the moment of time $ t_{i} $ when this task is added to the execution queue. For each task find out the moment of time when it will be completed.

The first line contains an integer number $ n $ $ (1

Print $ n $ space-separated integers. The $ i $ -th integer is the moment of time when the $ i $ -th task was completed.