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

Test 1

Input

Output

0
1
2

Test 2

Input

Output

Thông tin bài

Điểm:

100

Thời gian:

1.0s

Bộ nhớ:

256M

Input:

bàn phím

Output:

màn hình

Ngày tạo:

02/08/2026

Tác giả:

root

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Bình luận