Sửa ngày trong lịch sử

Cho dãy $n$ năm $y_1,y_2,\dots ,y_n$, trong đó mỗi $y_i$ là một số nguyên có đúng $4$ chữ số (từ $1000$ đến $9999$).

Hãy tìm dãy $z_1,z_2,\dots ,z_n$ thỏa mãn đồng thời các điều kiện sau:

• $1000\le z_i\le 2011$ với mọi $i$.
• $z_1\le z_2\le \dots \le z_n$ (dãy không giảm).
• $z_i$ khác $y_i$ ở nhiều nhất một vị trí chữ số (so sánh theo từng vị trí; $z_i$ luôn được viết bằng đúng $4$ chữ số và không được có chữ số $0$ ở vị trí đầu).

Nếu tồn tại nhiều dãy thỏa mãn, in ra một dãy bất kỳ. Nếu không tồn tại dãy nào, in ra No solution.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa một số nguyên $y_i$.

Dữ liệu ra

• Nếu có lời giải: in ra $n$ dòng, dòng thứ $i$ chứa số $z_i$.
• Nếu không có lời giải: in ra dòng duy nhất No solution.

Ràng buộc

• $1\le n\le 1000$
• $1000\le y_i\le 9999$

Ví dụ