B. Гарри Поттер и история магии
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

История магии, пожалуй, самый скучный предмет в Школе Чародейства и Волшебства Хогвартс. Гарри Поттер обычно спит на уроках истории, а лекции за него пишет Самопишущее Перо. Профессор Бинс, учитель истории магии, читает лекции настолько скучным и монотонным голосом, что он оказывает усыпляющее действие даже на Самопишущее Перо. Из-за этого Перо часто допускает ошибки, особенно в датах.

И вот в конце семестра профессор Бинс решил собрать у учеников пергаменты с лекциями на проверку. Рон Уизли в панике: если у Гарри есть хотя бы какие-то конспекты, пусть и с ошибками, то у него нет никаких, потому что на лекциях Рон тоже спал, а его перо давно сгрызла крыса Короста. Гермиона Грейнджер отказалась дать Рону свои конспекты, потому что, по ее мнению, все должны учиться самостоятельно. Поэтому Рону ничего не остается делать, кроме как переписывать конспекты Гарри.

Из-за ошибок Пера у Гарри вышла полнейшая путаница с датами: годы восстаний гоблинов и других важных для магического мира событий идут не по порядку, иногда даже встречаются даты из будущего. Теперь при переписывании Рон хочет изменить некоторые цифры так, чтобы даты шли в хронологическом (т.е. неубывающем) порядке и чтобы в конспектах не было дат позже 2011 года или раньше 1000 года. Чтобы полученная в результате последовательность была как можно ближе к той, которую диктовал профессор Бинс, Рон будет изменять не более одной цифры в каждой дате на другую цифру. Помогите ему сделать это.

Входные данные

В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 1000) — количество дат в конспектах Гарри. Следующие n строк содержат сами даты y1, y2, ..., yn, по одной в строке. Каждая дата является четырехзначным целым числом (1000 ≤ yi ≤ 9999).

Выходные данные

Выведите n чисел z1, z2, ..., zn (1000 ≤ zi ≤ 2011) — даты, получившиеся у Рона. Числа выводите по одному в строке. Числа zi должны образовывать неубывающую последовательность. Каждое число zi должно отличаться от соответствующей даты yi не более чем одной цифрой. Замена первой цифры числа на 0 не допускается. Если возможных решений несколько, выведите любое. Если решений нет, выведите «No solution» (без кавычек).

Примеры
Входные данные
3
1875
1936
1721
Выходные данные
1835
1836
1921
Входные данные
4
9999
2000
3000
3011
Выходные данные
1999
2000
2000
2011
Входные данные
3
1999
5055
2000
Выходные данные
No solution