Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Harry Potter and the History of Magic

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe History of Magic is perhaps the most boring subject in the Hogwarts school of Witchcraft and Wizardry. Harry Potter is usually asleep during history lessons, and his magical quill writes the lectures for him. Professor Binns, the history of magic teacher, lectures in such a boring and monotonous voice, that he has a soporific effect even on the quill. That's why the quill often makes mistakes, especially in dates.

So, at the end of the semester Professor Binns decided to collect the students' parchments with notes and check them. Ron Weasley is in a panic: Harry's notes may contain errors, but at least he has some notes, whereas Ron does not have any. Ronald also has been sleeping during the lectures and his quill had been eaten by his rat Scabbers. Hermione Granger refused to give Ron her notes, because, in her opinion, everyone should learn on their own. Therefore, Ron has no choice but to copy Harry's notes.

Due to the quill's errors Harry's dates are absolutely confused: the years of goblin rebellions and other important events for the wizarding world do not follow in order, and sometimes even dates from the future occur. Now Ron wants to change some of the digits while he copies the notes so that the dates were in the chronological (i.e. non-decreasing) order and so that the notes did not have any dates strictly later than 2011, or strictly before than 1000. To make the resulting sequence as close as possible to the one dictated by Professor Binns, Ron will change no more than one digit in each date into other digit. Help him do it.

Input

The first input line contains an integer *n* (1 ≤ *n* ≤ 1000). It represents the number of dates in Harry's notes. Next *n* lines contain the actual dates *y*_{1}, *y*_{2}, ..., *y*_{n}, each line contains a date. Each date is a four-digit integer (1000 ≤ *y*_{i} ≤ 9999).

Output

Print *n* numbers *z*_{1}, *z*_{2}, ..., *z*_{n} (1000 ≤ *z*_{i} ≤ 2011). They are Ron's resulting dates. Print each number on a single line. Numbers *z*_{i} must form the non-decreasing sequence. Each number *z*_{i} should differ from the corresponding date *y*_{i} in no more than one digit. It is not allowed to change the first digit of a number into 0. If there are several possible solutions, print any of them. If there's no solution, print "No solution" (without the quotes).

Examples

Input

3

1875

1936

1721

Output

1835

1836

1921

Input

4

9999

2000

3000

3011

Output

1999

2000

2000

2011

Input

3

1999

5055

2000

Output

No solution

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/21/2020 12:53:12 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|