The 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.
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*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">2</sub>, ..., *y*<sub class="lower-index">*n*</sub>, each line contains a date. Each date is a four-digit integer (1000 ≤ *y*<sub class="lower-index">*i*</sub> ≤ 9999).
none
3
1875
1936
1721
1075
1136
1221
4
9999
2000
3000
3011
1999
2000
2000
2011
3
1999
5055
2000
No solution
2
2037
2025
1037
2005
1
1234
1034
1
9876
1876
2
9988
8899
No solution
3
1095
1094
1095
1005
1014
1015
5
5555
4444
3333
2222
1111
No solution
3
2010
2011
2012
1010
1011
1012
5
1901
1166
1308
1037
1808
1001
1066
1108
1137
1208
5
1612
7835
8183
3368
1685
No solution
10
1501
1617
1368
1737
1800
1272
1019
1545
1035
1302
1001
1017
1068
1137
1200
1202
1219
1245
1335
1342
10
7577
1411
1864
1604
1589
1343
6832
1648
1222
1832
1577
1611
1664
1664
1689
1743
1832
1848
1922
1932
10
1110
1278
1283
7758
1183
1214
2970
1398
7515
1005
No solution
15
2003
1991
1741
1348
1258
1964
1411
1431
1780
1701
1787
1094
1108
1074
1942
1003
1091
1141
1148
1158
1164
1211
1231
1280
1301
1387
1394
1408
1474
1542
20
1749
1792
1703
1011
1289
1066
1947
1354
1693
1806
1645
1292
1718
1981
1197
1471
1603
1325
1057
1552
1049
1092
1103
1111
1189
1266
1347
1350
1393
1406
1445
1492
1518
1581
1597
1671
1673
1725
1757
1852
20
1639
1437
1054
1010
1872
1942
1315
1437
1226
1893
1712
1024
1410
1691
1188
1056
1642
1100
1893
1192
No solution
20
1025
1000
1026
1085
1354
1783
3490
1512
1553
1682
1695
1654
1679
1304
1574
1814
1854
1804
1928
1949
1005
1005
1006
1015
1054
1083
1490
1502
1503
1582
1595
1604
1609
1704
1774
1804
1804
1804
1828
1849
20
1011
1157
2181
6218
1766
8319
1364
6428
1476
4417
6618
1629
1747
1786
1787
2830
7671
1953
1275
1099
No solution
50
1230
6040
1035
1973
9096
5133
1146
1164
9195
5211
6212
1313
1953
1560
1382
2324
1343
1481
1555
1363
1487
1414
1525
1564
1561
9585
7590
1663
5625
1630
1630
3644
1164
1665
7678
1282
1626
1798
9755
7801
8809
1762
1867
1861
1826
1809
8902
1033
1774
9978
1030
1040
1045
1073
1096
1133
1136
1144
1195
1211
1212
1213
1253
1260
1282
1324
1333
1381
1455
1463
1467
1474
1505
1514
1521
1585
1590
1603
1625
1630
1630
1644
1664
1664
1678
1682
1686
1698
1755
1801
1809
1862
1862
1862
1866
1869
1902
1933
1974
1978
10
1014
1140
1692
1644
3647
1716
4821
9839
2882
1664
1004
1040
1092
1144
1647
1706
1821
1839
1882
1964
10
1075
1133
1393
1350
1369
1403
2643
1653
1756
7811
1005
1033
1093
1150
1169
1203
1643
1643
1656
1811
10
6025
1522
1835
2142
1414
9547
1456
6784
4984
3992
1025
1122
1135
1142
1214
1547
1556
1784
1984
1992
10
1074
1547
1554
1581
1170
8683
1434
4750
1866
1051
1004
1047
1054
1081
1100
1683
1734
1750
1766
1851
10
2008
3007
4066
1017
1920
1113
1317
4746
1972
1598
No solution
10
1171
1275
1680
7300
4742
2517
7980
1852
1993
5004
No solution
2
1999
1000
1099
1100
2
2004
1000
1004
1004
2
2099
1000
1099
1100
12
1000
1002
1021
1006
1001
1036
1038
1039
1098
1097
1029
1053
1000
1000
1001
1001
1001
1006
1008
1009
1018
1027
1027
1033
2
1011
1000
1001
1001
3
1012
1101
1000
1002
1100
1100
3
2000
3999
6011
1000
1999
2011
import sys

num_dates = int(sys.stdin.readline())
dates = []
for i in range(num_dates):
    date = int(sys.stdin.readline())
    dates.append(str(date))

least_date = 1000
for index in range(len(dates)):
    did_find_valid = False
    for i in range(4):
        for j in range(0, ord(dates[index][i]) - ord('0')):
            new_date = dates[index][0:i] + chr(j + ord('0')) + dates[index][i+1:]
            if int(new_date) >= least_date and int(new_date) <= 2011:
                did_find_valid = True
                least_date = int(new_date)
                dates[index] = new_date
                break
        if did_find_valid:
            break
    if not did_find_valid and dates[index] < dates[index-1]:
        print("No solution")
        sys.exit(0)

for date in dates:
    print(date)
