Xét một vi mạch (IC) có \(n\) đầu vào ở phía trên và \(n\) đầu ra ở phía dưới. Ở mỗi phía, các đầu được đánh số \(1,2,\ldots,n\) từ trái sang phải. Mỗi đầu vào được nối tới đúng một đầu ra và mỗi đầu ra nhận tín hiệu từ đúng một đầu vào.

Ta mô tả một IC bằng dãy \((a_1,\ldots,a_n)\), trong đó \(a_i\) là số thứ tự của đầu vào nối tới đầu ra \(i\). Chẳng hạn, IC \((2,3,1)\) nối đầu vào \(2\) tới đầu ra \(1\), đầu vào \(3\) tới đầu ra \(2\), và đầu vào \(1\) tới đầu ra \(3\).

Với \(n=3\), có sáu loại IC: \((1,2,3)\), \((1,3,2)\), \((2,1,3)\), \((2,3,1)\), \((3,1,2)\) và \((3,2,1)\).

Khi mắc các IC nối tiếp, đầu ra \(i\) của IC trước được nối với đầu vào \(i\) của IC sau. Ví dụ, mắc nối tiếp năm IC đều có dạng \((2,3,1)\) sẽ có tác dụng giống IC \((3,1,2)\): các đầu ra cuối cùng \(1,2,3\) lần lượt nhận tín hiệu từ các đầu vào ban đầu \(3,1,2\).

Cho \(n\), \(k\) và hoán vị \((a_1,\ldots,a_n)\) của các số từ \(1\) đến \(n\). Hãy xác định có thể mắc nối tiếp \(k\) IC cùng loại để có tác dụng giống IC \((a_1,\ldots,a_n)\) hay không. Nếu có, hãy đưa ra một loại IC thỏa mãn. Nếu có nhiều đáp án, được phép đưa ra bất kỳ đáp án nào.

Dữ liệu vào

Đọc từ đầu vào chuẩn, gồm \(n+1\) dòng:

• Dòng đầu chứa hai số nguyên \(n,k\), phân cách bằng dấu cách.
• Dòng thứ \(i+1\) (\(1\le i\le n\)) chứa số nguyên \(a_i\).

Dữ liệu ra

Ghi kết quả ra đầu ra chuẩn.

Nếu có loại IC thỏa mãn, ghi \(n\) dòng mô tả IC đó. Dòng thứ \(i\) (\(1\le i\le n\)) chứa số thứ tự của đầu vào nối tới đầu ra \(i\) của IC cần tìm. Dãy được ghi ra phải là một hoán vị của các số từ \(1\) đến \(n\).

Nếu không tồn tại loại IC thỏa mãn, chỉ ghi một dòng chứa 0.

Ràng buộc

• \(1\le n\le10\,000\).
• \(1\le k\le10\,000\).
• \(1\le a_i\le n\) (\(1\le i\le n\)); các \(a_i\) đôi một khác nhau.

Phân nhóm

Các bộ dữ liệu được chấm độc lập; không có điều kiện ràng buộc riêng cho từng nhóm.

• Các bộ dữ liệu \(01\)–\(05\): \(20\) điểm mỗi bộ, tổng cộng \(100\) điểm; áp dụng toàn bộ ràng buộc trên.

Ví dụ

3 5
3
1
2

2
3
1

4 4
2
1
4
3

0