Submit
 

M : Dial

Time Limit : 2 sec, Memory Limit : 262144 KB

Problem M: Dial

Problem

ダイヤル式の南京錠がある。この南京錠には、5つのダイヤルと、決定ボタンが用意されている。

5つあるダイヤルを回転させて16進数で5ケタの整数を作り、決定ボタンを押して入力すると、入力した値とパスワードが一致していれば開く仕組みになっている。5つのダイヤルそれぞれには

0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,0,1,2, ...

の順で文字が現れるように書かれている。

持ち主はパスワードを忘れてしまった。しかし、パスワードの5ケタのうち、1つのケタだけが偶数で残り4つは奇数であったことは覚えている。 ただし、偶数とは0,2,4,6,8,a,c,eであり、奇数とは1,3,5,7,9,b,d,fである。

またこの鍵は不良品で、以下の条件でパスワードと異なる数字を入力しても開いてしまうことが分かっている。本来、入力した整数とパスワードが5つのケタすべてについて一致していなければ鍵は開かない。しかし、パスワードの偶数となっているケタがiケタ目だった場合、iケタ目の一致判定を行うとき、その偶数の前後にある奇数が入力されていた場合でもiケタ目は一致していると誤判定されてしまうのだ。

例えば、パスワードが"57677"の南京錠ならば、'6'の前後には'5'と'7'の奇数があるため"57677"のほかに、"57577"や"57777"を入力したときでも開いてしまう。 同様に、パスワードが"130bd"の南京錠ならば、'0'の前後には'1'と'f'の奇数があるため"130bd"のほかに、"13fbd"や"131bd"を入力したときでも開いてしまう。

今、パスワードの候補がN個あり、それらのうちどれか1つが正解のパスワードであることが分かっている。しかたがないので持ち主は、鍵が開くまで何度も整数を入力して試し続けることにした。持ち主はできるだけ決定ボタンを押す回数を少なくしたい。

持ち主が最適な戦略をとったとき、最大で何回決定ボタンを押さなければならないだろうか? その回数を出力せよ。 また、実際に最大となるときに入力する整数の集合を昇順に出力せよ。 答えが一意に定まらない場合は、辞書順で最小となるものを出力せよ。

Input

入力は以下の形式で与えられる。

N
password1
password2
...
passwordN

1行目にNが与えられる。
2行目からN+1行目のi行目には、パスワードの候補を表す5ケタの16進数を表す文字列passwordiが与えられる。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ N ≤ 6000
  • passwordipasswordj ( i < j )
  • 文字列は、0から9の数字または英小文字aからfの5文字で構成され、そのうち1文字は偶数であり、他の4文字は奇数である

Output

鍵が開くまでに最適な戦略をとったときの決定ボタンを押す回数の最大値を1行に出力せよ。 続いて、最大となるときに入力する整数の集合を昇順に出力せよ。 もし、答えが一意に定まらない場合は、辞書順で最小となるものを出力せよ。

Sample Input 1

1
0111f

Sample Output 1

1
0111f

Sample Input 2

3
57567
57587
0d351

Sample Output 2

2
0d351
57577

Sample Input 3

6
1811b
1a11b
f3b1e
f3b1c
b0df3
bedf3

Sample Output 3

3
1911b
bfdf3
f3b1d