경주 트랙

$n$명의 선수가 여러 바퀴를 도는 경주 트랙이 있다. 각 선수에게는 고유한 최고 속도가 있다. 이 경주 트랙에서는 매 바퀴의 결승선 근처에서만 추월할 수 있다. 어떤 선수가 더 느린 선수에게 가까워지면 결승선에 도달할 때까지 그 선수의 뒤에 머문다. 결승선에서는 동시에 결승선을 통과하는 모든 선수가 자신의 최고 속도로 다시 달리기 시작한다(따라서 더 빠른 선수가 더 느린 선수를 추월한다). 처음에 모든 선수는 결승선에서 출발한다. 각 선수의 한 바퀴 주행 시간과 완주해야 하는 바퀴 수가 주어질 때, 각 선수가 경주를 완주하는 시각을 계산한다.

첫째 줄에 선수의 수를 나타내는 정수 $n$ ($1 \leq n \leq 5\,000$)이 주어진다. 이어지는 $n$개의 줄에는 각 선수의 한 바퀴 주행 시간과 완주해야 하는 바퀴 수가 주어진다. $i$-번째 줄에는 두 정수 $t_i$와 $c_i$ ($1 \leq t_i \leq 10^6$, $1 \leq c_i \leq 1\,000$)이 주어지며, 이는 선수 $i$의 한 바퀴 주행 시간과 완주해야 하는 바퀴 수이다. 선수들은 속도의 내림차순으로 정렬되어 있다. 즉, $t_1 \leq t_2 \leq \ldots \leq t_n$이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 선수 $i$가 경주를 완주하는 시각을 출력해야 한다.