信息技术正在发展并日益渗透到人类活动的各个领域。令人难以置信的是,最现代的技术被用于农业!
一个大农场有一个草地,里面有放牧的羊。总共有 n 只羊,每只羊都包含一个从 1 到 n 的唯一数字 - 因为需要区分羊,你需要记住每只羊的信息,而且它们非常相似!草地由无数个区域组成,编号从 1 到无穷大。已知羊i喜欢里到里的区域。
有两个牧羊人在照顾羊:第一和第二。一大早起床,牵着羊群在草坪上吃草。第二次在晚上来收集所有的羊。
一天早上,先比平时起得晚了一点,没时间牵羊到草坪上吃草。因此,如果有两个羊都喜欢的地区,他就把每两只羊绑在一起。一是觉得这样会好一点——二是晚上的工作量会少一些,因为羊不会散太多,互相拴着!
晚上,第二个来到草坪上,聚集羊群并试图将它们排成一排。但无论他如何努力,羊都不会按照老二的意愿排列!老二既没有力气,也没有能力解开羊群,所以他就让羊群保持原状,但有一个条件:他要把羊排成一排,使两只被绑住的羊之间的最大距离尽可能小。羊之间的距离是介于两者之间的行中羊的数量。
帮助第二找到正确的安排。
输入
第一个输入行包含一个整数 n (1 ≤ n ≤ 2000)。以下 n 行中的每一行包含两个整数 li 和 ri (1 ≤ li, ri ≤ 109; li ≤ ri)。
输出
在单个输出行中打印 n 个空格分隔的数字 - 所寻求的羊的排列。该行中的第 i 个值必须代表最优排列行中从左起第 i 个位置的羊的数量。
如果有多个最佳排列,则打印其中任意一个。
示例
输入 #1
3 1 3 5 7 2 4
输出 #1
1 3 2
输入 #2
5 1 5 2 4 3 6 1 7 2 6
输出 #2
2 1 3 5 4
输入 #3
4 1 3 4 6 5 7 2 3
输出 #3
1 4 2 3