code festival 2014 上海

A - Lock


Time limit時間制限 : 4sec / Memory limitメモリ制限 : 256MB

Problem

Alice has a box locked with n digits dial lock. Each dial of the lock can be set to a digit from 0 to 9. Unfortunately, she forgot the passcode (of n digits). Now she will try all possible combinations of digits to unlock the key.

She can do one of the following procedure each time.

  • Choose 1 dial and add 1 to that digit. (If the digit chosen was 9, it will be 0).
  • Choose 1 dial and subtract 1 from that digit. (If the digit chosen was 0, it will be 9).

Curiously, she wants to try all combinations even if she found the correct passcode during the trials. But it is a hard work to try all the 10^n combinations. Help her by showing the way how to make the procedure less as possible.

Initially, the combination of digits of the lock is set to 00..0.

Calculate m, the minimum number of procedures to try all combinations of digits, and show the m+1 combinations of digits after each procedures, including the initial combination 00..0. If there are more than one possible answer, you may choose any one of them.

Checking if the current combination of digits matches the passcode doesn't count as a procedure.


Input

Input is given in the following format.

n
  • On the first line, you will be given n (1 \leq n \leq 5), the number of digits of the dial lock.

Output

On the first line, output m, the minimum number of procedures to try all combinations of digits.

On the following m+1 lines, output the combination of digits that appears during the trial in order. If there are more than 1 possible answer, you may choose any one of them. Make sure to insert a line break at the end of the last line.


Input Example 1

1

Output Example 1

9
0
1
2
3
4
5
6
7
8
9

Don't forget to output the minimum number of procedures 9 on the first line.

On the following lines, note that you have to output m+1 lines including the initial combination 0.


Input Example 2

2

Output Example 2

99
00
01
02
03
04
05
06
07
08
09
19
18
17
16
15
14
13
12
11
10
20
21
22
23
24
25
26
27
28
29
39
38
37
36
35
34
33
32
31
30
40
41
42
43
44
45
46
47
48
49
59
58
57
56
55
54
53
52
51
50
60
61
62
63
64
65
66
67
68
69
79
78
77
76
75
74
73
72
71
70
80
81
82
83
84
85
86
87
88
89
99
98
97
96
95
94
93
92
91
90

Submit提出する