排队问题

题目描述

有$n$个人排队，第$i$个人身高为$a_{i}$（保证每个人身高不同），要么左边有$b_{i}$个比她高的人，要么右边有$b_{i}$个比她高的人。找出字典序最小的满足条件的身高序列。

输入格式

第一行输入一个整数$n$，表示人数。

接下来$n$行，每行两个整数$a_{i}$，$b_{i}$。

输出格式

输出一行，这个队列里从前到后的每个人的身高。如果有多个人答案满足题意，输出字典序最小。如果不存在满足题意的队列，输出impossible。

数据范围与提示

• 对于$40\%$的数据，$n \leq 10$；
• 对于$60\%$的数据，$n \leq 1000$；
• 对于$90\%$的数据，$n \leq 10^{5}$；
• 对于$100\%$的数据，$1 \leq n \leq 10^{6}$，其中$1 \leq a_{i} \leq 2^{31}$。

样例

4
4 1
3 1
6 0
2 0

2 4 3 6

6
1 5
8 0
3 1
4 0
2 0
6 0

1 2 4 3 6 8

见queue3.in

见queue3.out