CF65B Harry Potter and the History of Magic

魔法史可能是霍格沃茨魔法学校里最无聊的课程。哈利·波特通常会在历史课上睡着，他的魔法羽毛笔会代替他记笔记。魔法史教授宾斯的讲课声音单调又无趣，甚至连羽毛笔都昏昏欲睡。因此，羽毛笔经常会记错，特别是年份。 于是，在学期末，宾斯教授决定收集学生们的羊皮纸笔记进行检查。罗恩·韦斯莱陷入了恐慌：哈利的笔记虽然可能有错误，但至少还有笔记，而罗恩却什么都没有。罗恩上课一直在睡觉，他的羽毛笔还被老鼠斑斑吃掉了。赫敏·格兰杰拒绝把她的笔记借给罗恩，因为她认为每个人都应该独立学习。因此，罗恩除了抄哈利的笔记，别无选择。 因为羽毛笔的失误，哈利的年份已经完全混乱：哥布林起义的年份和其他巫师世界重大事件的日期都没有按顺序排列，有时甚至还出现了来自未来的日期。现在罗恩打算在抄写时，对每个年份只更改不超过一位数字，使得所有日期按时间顺序（即非递减顺序）排列，并且每个日期不得晚于 $2011$ 年、也不得早于 $1000$ 年。为使结果尽量接近宾斯教授讲课内容，罗恩抄写时每个年份最多只能更改一位数字。 请帮助罗恩完成这项工作。

第一行输入一个整数 $n$（$1 \leq n \leq 1000$），表示哈利笔记里的年份个数。接下来的 $n$ 行，每行一个年份 $y_i$，均为四位整数（$1000 \leq y_i \leq 9999$）。

输出 $n$ 个数字 $z_1, z_2, ..., z_n$（$1000 \leq z_i \leq 2011$），分别表示罗恩抄写后的年份。每个数字占一行。要求 $z_i$ 构成非递减序列，并且每个 $z_i$ 与所对应的 $y_i$ 相比不超过一位数字不同，且不能把数字的第一位改为 $0$。如果有多个可行解，输出任意一个即可。如果无解，输出“No solution”。

由 ChatGPT 5 翻译