Kiệt có hai dãy số gồm ~N~ số ~A_1, A_2, ..., A_N~ và ~B_1, B_2, ..., B_N~. Trong đó ~B_i~ là tổng các chữ số của ~A_i~. Tuy nhiên, do hay quên nên Kiệt đã lạc mất dãy ~A~ và chỉ còn dãy ~B~. Kiệt muốn tạo lại một mảng ~A~ mới có ~N~ số sao cho thỏa điều kiện ~B_i~ là tổng các chữ số của ~A_i~. Để dễ nhớ, Kiệt muốn dãy ~A~ là một dãy tăng nghiêm ngặt và ~A_N~ là nhỏ nhất. Hãy giúp Kiệt tạo ra một mảng ~A~ mới nhé~!~

Lưu ý: Một dãy ~A~ gồm ~N~ phần tử được gọi là dãy tăng nghiêm ngặt nếu ~A_{i - 1} < A_i~ với ~(2 \le i \le N)~.

Input

• Dòng đầu chứ ~N (1 \le N \le 300)~ là số lượng phần tử của dãy số ~A, B~,
• ~N~ dòng tiếp, dòng thứ ~i~ gồm giá trị của ~B_i (1 \le B_i \le 300)~.

Output

Kết quả bao gồm ~N~ dòng, dòng thứ ~i~ có giá trị ~A_i~ không có số ~0~ vô nghĩa ở đầu.

Lưu ý: Nếu có nhiều dãy ~A~ thõa mãn, in một dãy bất kì.

Sample

Input #1

3
3
2
1

Output #1

12
20
100

Input #2

3
1
2
3

Output #2

1
2
3