Нагадаємо, що розміщення з ~n~ по ~k~ – виборки по ~k~ елементів з ~n~ можливих, причому порядок елементів у вибірці важливий («1 2» відрізняється від «2 1»).

Наприклад, повний перелік всіх можливих розміщень з 3 по 2: (1,2), (1,3), (2,1), (2,3), (3,1), (3,2).

Напишіть програму, яка за заданими ~n~ і ~k~ генеруватиме всі можливі розміщення з чисел 1, 2, ..., ~n~ по ~k~. Розміщення повинні виводитися в лексикографічному (словниковому, але за числами) порядку.

Вхідні дані

В єдиному рядку через пропуск задано два числа – спочатку ~n~, потім ~k~.

Виконуються умови: ~k\leqslant n\leqslant 20~; ~\quad~ ~1\leqslant k\leqslant 7~; ~\quad~ ~1\leqslant A_n^k < 10^4~ (де ~A_n^k~ – кількість розміщень, які слід згенерувати).

Результати

Виведіть знайдені розміщення, кожне в окремому рядку, в лексикографічному (за числами) порядку. Усередині рядка числа повинні відділятися один від одного одиничними пробілами.

Приклади

Вхід

3 2

Результат

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

Примітки

Під «лексикографічним (за числами) порядком» мається на увазі: спочатку треба виводити всі розміщення, де на першому (крайньому зліва) місці 1, потім усі, де на першому місці 2, тощо, насамкінець усі, де на першому місці ~n~. У свою чергу, всі розміщення, де перші числа однакові між собою, мають бути відсортовані за другими числами; всі розміщення, де однакові як перші так і другі числа, мають бути відсортовані за третіми; тощо.

Примітка «за числами» означає, що якби спочатку сформували всі розміщення як рядки, і відсортували рядки, то порядок виявився б таким самим при ~n\leqslant 9~, але при ~n\geqslant 10~ з'являється відмінність. Наприклад, при ~n=10~ у цій задачі потрібно виводити розміщення, що починаються з 10, наприкінці, а якби поформували рядки й відсортували їх як рядки, то розміщення, що починаються з 10, потрапили б між розміщеннями, що починаються з 1, і розміщеннями, що починаються з 2 (що в цій задачі не буде зараховуватися).