The Treasure of the Password Box

After nineteen years of exploration, humanity has finally discovered the treasure of the universe, hidden inside a password box. According to intelligence, the original password was a sequence of \(n\) digits \(a\). However, when the password was entered, the box showed no reaction.

It turns out that during these nineteen years, cosmic rays altered the password. The new password is derived from the original \(a\) by changing exactly \(t\) digits, where \(0 \le t \le k\). For each digit that is changed, the digit is either increased or decreased by \(1\). In particular, if the original digit is \(0\), decreasing it yields \(9\); and if the original digit is \(9\), increasing it yields \(0\).

Your task is, given \(n\), \(a\), and \(k\), to output all possible passwords that can open the box. The passwords should be printed in ascending order (when viewed as numbers after removing any leading zeros). Note that if a password has leading zeros, you must not output them.

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\) — the length of the password.
• The second line contains a string \(a\) of \(n\) digits (possibly with leading zeros) representing the original password.
• The third line contains an integer \(k\) — the maximum number of digits that can be changed.

outputFormat

Output each possible valid password (after removing any leading zeros) on a separate line, in ascending numerical order.

sample

2
09
1

0
8
9
19
99