有一个赛道，共有 $n$ 名选手在此完成多圈比赛。每名选手都有各自的最大速度。在这个赛道上，超车仅能在每一圈的终点线附近进行：当一名选手追上前方较慢的选手时，他会保持在对方身后，直到到达终点线。在终点线处，所有同时到达的选手会恢复各自的最大速度继续行驶（因此速度较快的选手会超过较慢的选手）。起初，所有选手都从终点线出发。给定每名选手的单圈用时和需要完成的圈数，计算他们各自完成比赛的时间。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5\,000$)，表示选手人数。接下来的 $n$ 行包含选手的单圈用时和需要完成的圈数：第 $i$ 行包含两个整数 $t_i$ 和 $c_i$ ($1 \le t_i \le 10^6$, $1 \le c_i \le 1\,000$)，分别表示选手 $i$ 的单圈用时和需要完成的圈数。选手已按速度从快到慢排序，即 $t_1 \le t_2 \le \dots \le t_n$。

输出格式

输出 $n$ 行；第 $i$ 行必须包含选手 $i$ 完成比赛的时间。

样例

样例输入 1

2
4 8
7 6

样例输出 1

36
42