← 返回题目列表

Codeforces · 65/B

B. 哈利·波特与魔法史

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

魔法史也许是霍格沃茨魔法学校中最无聊的科目。哈利·波特在历史课上通常会睡觉,他的神奇羽毛笔会为他写讲稿。宾斯教授,魔法史老师,讲课的声音枯燥单调,连羽毛笔都有催眠作用。这就是为什么羽毛笔经常出错,尤其是在日期方面。

因此,学期结束时,宾斯教授决定收集学生的带有笔记的羊皮纸并进行检查。罗恩·韦斯莱惊慌失措:哈利的笔记可能有错误,但至少他有一些笔记,而罗恩却没有。罗纳德在讲座期间也一直在睡觉,他的羽毛笔被他的老鼠斑斑吃掉了。赫敏格兰杰拒绝给罗恩她的笔记,因为在她看来,每个人都应该自己学习。因此,罗恩别无选择,只能抄写哈利的笔记。

由于羽毛笔的错误,哈利的日期完全混乱:妖精叛乱的年份和魔法世界的其他重要事件没有按顺序排列,有时甚至会发生来自未来的日期。现在,Ron 想要在复制笔记时更改一些数字,以便日期按时间顺序(即非递减)顺序排列,并且笔记中没有任何严格晚于 2011 年或严格早于 1000 的日期。为了使结果序列尽可能接近 Binns 教授口述的序列,Ron 将每个日期中不超过一位的数字更改为其他数字。帮他做吧。

输入

第一个输入行包含一个整数 n (1 ≤ n ≤ 1000)。它代表哈利笔记中的日期数量。接下来的 n 行包含实际日期 y1, y2, ..., yn,每行包含一个日期。每个日期都是一个四位整数 (1000 ≤ yi ≤ 9999)。

输出

打印 n 个数字 z1, z2, ..., zn (1000 ≤ zi ≤ 2011)。它们是 Ron 的结果日期。将每个数字打印在一行上。数字 zi 必须构成非递减序列。每个数字 zi 与相应日期 yi 的差异不得超过一位。不允许将数字的第一位更改为 0。如果有多种可能的解决方案,请打印其中任何一个。如果没有解决方案,请打印“无解决方案”(不带引号)。

示例

输入 #1

3
1875
1936
1721

输出 #1

1835
1836
1921

输入 #2

4
9999
2000
3000
3011

输出 #2

1999
2000
2000
2011

输入 #3

3
1999
5055
2000

输出 #3

No solution