Enigmatic Number

Interview

Time limit2sMemory limit1024 MB

Summary

Split the decimal string N into the fewest pieces taken from a given set of up to 1000 numbers below 1000, using each number at most once.

Level: Medium5 of 10
Topics: Dynamic programming, String, Hash map
Solved: No attempts yet

Statement

John is a junior researcher at the Research Institute for the Meaning of Life. Recently he discovered that the decimal number $N$ holds knowledge that can shed light on some issues of human life. John is selfish, however, and does not want to share his discovery. So he decided to memorize this number and destroy every record of it.

Unfortunately John is a bit distracted and forgetful, so he will memorize $N$ in the following way. He has a set of $K$ numbers connected with his life, which he remembers very well, even better than his birthday. All of these numbers have at most three digits.

John tries to represent $N$ as a concatenation of numbers from this set. For example, concatenating 1 and 2 gives 12 or 21, depending on the order. No number may be used twice, but it is not required to use all of them. John wants a representation with as few numbers as possible. Write a program that finds such a representation.

Input

The first line contains an integer $N$ ( $1 \le N < 10^{45}$ ). The second line contains an integer $K$ ( $1 \le K \le 1000$ ), the size of the set. The third line contains the $K$ memorable numbers ( $0 \le a_i < 1000$ ). All numbers in the set are different and have no extra leading zeroes.

Output

On the first line, print an integer $M$ , the size of the partition. On each of the following $M$ lines, print one number of the partition, in the order in which they must be concatenated to obtain $N$ .

If several partitions satisfy the conditions, print any of them. It is guaranteed that at least one valid partition exists.

Examples2

Example 1
Input
```
123
4
1 3 12 23
```
Expected output
```
2
12
3
```
Example 2
Input
```
123
4
1 2 3 123
```
Expected output
```
1
123
```