题目描述

有 $n$ 个光头强，第 $i$ 个光头强会在第 $i$ 到第 $a_i(i≤a_i≤n)$ 天出现，它的攻击力为 $b_i$。其中对于所有 $i(1≤i<n)$，满足 $a_i≤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≤n≤10^5,1≤b_i≤10^5$。