有$n$个生物，第$i$个生物会在第$i$到第$a_i(i\leq a_i\leq n)$天出现，它的攻击力为$b_i$。其中对于所有$i(1\leq i < n)$，满足$a_i\leq a_{i+1}$。请输出每天出现的生物的攻击力的最大值。

输入格式

第一行一个整数$n$。

接下来$n$行，每行两个整数$a_i, b_i$。

输出格式

一共$n$行，每行一个数表示答案。

第$i$个整数表示第$i$天出现的生物的攻击力的最大值。

样例输入

5
3 8
4 9
5 1
5 6
5 1

样例输出

8
9
9
9
6

数据规模

对于所有数据，保证$1\leq n\leq 10^5, 1\leq b_i\leq 10^5$。