魔法史也许是霍格沃茨魔法学校中最无聊的科目。哈利·波特在历史课上通常会睡觉,他的神奇羽毛笔会为他写讲稿。宾斯教授,魔法史老师,讲课的声音枯燥单调,连羽毛笔都有催眠作用。这就是为什么羽毛笔经常出错,尤其是在日期方面。
因此,学期结束时,宾斯教授决定收集学生的带有笔记的羊皮纸并进行检查。罗恩·韦斯莱惊慌失措:哈利的笔记可能有错误,但至少他有一些笔记,而罗恩却没有。罗纳德在讲座期间也一直在睡觉,他的羽毛笔被他的老鼠斑斑吃掉了。赫敏格兰杰拒绝给罗恩她的笔记,因为在她看来,每个人都应该自己学习。因此,罗恩别无选择,只能抄写哈利的笔记。
由于羽毛笔的错误,哈利的日期完全混乱:妖精叛乱的年份和魔法世界的其他重要事件没有按顺序排列,有时甚至会发生来自未来的日期。现在,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