Dãy Chọn Không Lặp · canuc80k0702

Cho hai số nguyên $n$ và $m$ . Hãy liệt kê mọi dãy $(x_{1}, x_{2}, \dots, x_{m})$ sao cho mỗi $x_{i}$ thuộc $[1, n]$ và các phần tử trong cùng một dãy đôi một khác nhau. Các dãy phải xuất hiện theo thứ tự từ điển tăng dần.

Input

Dòng duy nhất chứa hai số nguyên $n$ và $m$ .

Output

Mỗi dãy hợp lệ được in trên một dòng; các phần tử cách nhau bởi một dấu cách.

Constraints

$1 \leq m \leq n \leq 8$ .

Scoring

Subtask $1$ ( $50%$ ): $n \leq 5$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

3 2

Output

Giải thích: Có sáu dãy độ dài $2$ dùng các số khác nhau trong ${1, 2, 3}$ . Thứ tự thử giá trị tăng dần cho kết quả $1$ $2, 1$ $3, 2$ $1, 2$ $3, 3$ $1, 3$ $2$ .

Ý tưởng: Duy trì dãy đang xây và mảng chosen[value] cho biết một số đã xuất hiện trong tiền tố hay chưa. Tại mỗi vị trí, duyệt các giá trị từ 1 đến n; chỉ chọn giá trị chưa dùng, đánh dấu nó, đệ quy, rồi bỏ đánh dấu khi quay lui.
Ý tưởng: Khi tiền tố đạt độ dài m, in dãy. Duyệt ứng viên theo thứ tự tăng giúp đầu ra tự động có thứ tự từ điển.
Chứng minh tính đúng đắn: Mảng đánh dấu bảo đảm không dãy nào chứa một giá trị hai lần. Với một dãy hợp lệ bất kỳ, tại từng vị trí, giá trị cần chọn chưa xuất hiện trong tiền tố nên nhánh tương ứng luôn khả dụng; do đó thuật toán sinh đủ mọi dãy. Chuỗi lựa chọn ở các vị trí xác định duy nhất một lá, nên không có hai lần sinh cùng một dãy. Thứ tự thử giá trị tăng dần bảo đảm thứ tự từ điển.
Độ phức tạp: Có P(n,m)=n!/(n-m)! dãy. Tính cả việc in, thời gian là O(m·P(n,m)); bộ nhớ phụ O(n+m).