← 返回题目列表

Codeforces · 141/C

C. 队列

中文机器翻译题面 查看原题

在 Main Berland Bank,n 个人在收银台排队,每个人都知道他/她的身高 hi,以及队列中其他人的身高。他们每个人都记住数字ai——有多少人比他/她高并在他面前排队。

过了一会儿,收银员午休,排队的人按随机顺序坐在候诊室的椅子上。

午休结束后,发现没人能记得队列里人的确切顺序,但每个人都记得他的号码ai。

你的任务是在可能的情况下恢复人们排队的顺序。可能有多个可接受的订单,但您需要找到其中任何一个。另外,您需要打印一组可能的数字 hi - 队列中人员的身高,以便数字 ai 是正确的。

输入

第一个输入行包含整数 n — 队列中的人数 (1 ≤ n ≤ 3000)。那么n行包含对人的描述为“namei ai”(一行一个描述),其中namei是一个由小写拉丁字母组成的非空字符串,长度不超过10个字符(第i个人的名字),ai是一个整数(0≤ai≤n-1),表示队列中排名较高且站在i人前面的人的数量。保证所有名称都是不同的。

输出

如果队列中的人员顺序不可接受,则打印包含“-1”(不带引号)的单行。否则,将人打印为 n 行“namei hi”,其中 hi 是 1 到 109(含)之间的整数,即名字为 namei 的人的可能身高。按照人员在队列中站立的顺序打印人员,从队列的头部开始到队列的尾部。数字 hi 不一定是唯一的。

示例

输入 #1

4
a 0
b 2
c 0
d 0

输出 #1

a 150
c 170
d 180
b 160

输入 #2

4
vasya 0
petya 1
manya 3
dunay 3

输出 #2

-1