Mô tả

Trong một tiệm bánh có N loại bánh khác nhau. Uolevi muốn chọn ra K chiếc bánh để mang về và được phép chọn nhiều chiếc cùng loại.

Hãy sử dụng đệ quy để liệt kê tất cả các chỉnh hợp lặp độ dài K được tạo từ tập:

{1, 2, ..., N}

Mỗi chỉnh hợp được in trên một dòng, các phần tử cách nhau bởi một dấu cách.

Dữ liệu vào

Hai số nguyên dương N và K (1 ≤ K ≤ N ≤ 8).

Dữ liệu ra

In ra tất cả các chỉnh hợp lặp gồm K phần tử được chọn từ tập {1, 2, ..., N}, mỗi chỉnh hợp trên một dòng.

Ví dụ 1

Input

1 1

Output

1

Ví dụ 2

Input

2 1

Output

1
2

Ví dụ 3

Input

2 2

Output

1 1
1 2
2 1
2 2

Ví dụ 4

Input

3 1

Output

1
2
3

Ví dụ 5

Input

3 2

Output

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3