경주 트랙

원형 경주 트랙에서 $n$명의 선수가 정해진 바퀴 수를 채운다. 선수마다 최고 속도가 다르다. 선수 $i$는 최고 속도로 한 바퀴를 도는 데 $t_i$의 시간이 걸리고, $c_i$바퀴를 완주해야 한다.

이 트랙에서 추월은 결승선에서만 일어난다. 한 바퀴를 도는 도중에 앞서 달리던 느린 선수를 따라잡으면, 뒤따라온 선수는 그 바퀴가 끝날 때까지 바로 뒤에 붙어 같은 속도로 달린다. 그래서 두 선수는 같은 순간에 결승선을 통과한다.

결승선을 같은 순간에 통과한 선수는 모두 그 지점에서 다시 최고 속도로 달리기 시작한다. 빠른 선수가 느린 선수를 앞선다.

출발할 때는 모든 선수가 결승선에 함께 서 있다. 마지막 바퀴를 마친 선수는 곧바로 트랙을 떠나고, 그 뒤로는 아무도 막지 않는다.

각 선수의 한 바퀴 시간과 완주할 바퀴 수가 주어질 때, 선수마다 완주하는 시각을 구하시오.

첫째 줄에 선수의 수 $n$이 주어진다. ($1 \le n \le 5000$)

다음 $n$개 줄 중 $i$번째 줄에 선수 $i$의 한 바퀴 시간 $t_i$와 완주할 바퀴 수 $c_i$가 주어진다. ($1 \le t_i \le 10^6$, $1 \le c_i \le 1000$)

선수는 빠른 순서로 주어진다. 즉 $t_1 \le t_2 \le \dots \le t_n$이다.

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