Dãy tam phân

Các nhà khoa học vừa thu được tín hiệu từ một nền văn minh ngoài hành tinh. Tín hiệu này là một chuỗi có độ dài \(N\), chỉ bao gồm ba ký tự: \(0, 1, 2\). Hãy sử dụng đệ quy để liệt kê tất cả các chuỗi tam phân có độ dài \(N\) mà tín hiệu đó có thể có.

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 10\)).

Output

In ra tất cả các chuỗi tam phân có độ dài \(N\), mỗi chuỗi trên một dòng, theo thứ tự từ điển tăng dần.

Example

1

0
1
2

2

00
01
02
10
11
12
20
21
22