Input Jumbled Key#12830

Input Jumbled Key

4 seconds
512 megabytes
Very hard

The digital lock used to access the university datacenter consists of five wheels with hexadecimal digits written on each wheel.

The digits are written in the order "0123456789ABCDEF", if rotate wheel after 'F' digit then '0' will appear again and so on.

The new system administrator found that information about the key opening the door is jumbled. He managed to get the list of possible passwords where exactly one is correct. Additionally he was told that:

The system administrator wants to find the sequence of keys to enter it in the lock one by one that:

  1. May contain keys from the list as well as keys not listed in there.

  2. Ensures that lock will be opened at the end of the sequence or earlier.

  3. Contains the minimum possible number of keys.

  4. Is lexicographically minimal among all sequences, conforming 1-3.

Help him to find such a sequence.

Input

First line of the input contains one integer (1 \le N \le 6000). Each of the following lines contains one key — the five-digit string consisting of the hexadecimal digits ('0' - '9' and 'A' - 'F'). You may assume that exactly one digit in any of the keys is even.

Output

In first line of the input print one integer — minimum number of keys in the sysadmin's list. Then following lines shall contain the keys in order they shall be entered to the lock. Note that you shall select lexicographically minimal list of keys among all possible shortest lists.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading