Король Берляндии устраивает бал! На него приглашены $$$n$$$ пар, они пронумерованы от $$$1$$$ до $$$n$$$. Каждая пара состоит из одного мужчины и одной женщины. Каждый танцор (то есть и мужчина, и женщина) должен надеть одноцветный костюм. Цвет каждого костюма можно обозначить целым числом от $$$1$$$ до $$$k$$$ включительно.

Пусть $$$b_i$$$ — цвет костюма мужчины, а $$$g_i$$$ — цвет костюма женщины в $$$i$$$-й паре. Вам необходимо выбрать цвета костюмов для каждого из танцоров (то есть значения $$$b_1, b_2, \dots, b_n$$$ и $$$g_1, g_2, \dots g_n$$$) таким образом, что:

1. для каждого $$$i$$$: $$$b_i$$$ и $$$g_i$$$ должны быть целыми числами от $$$1$$$ до $$$k$$$ включительно;
2. не существует двух абсолютно одинаковых пар, то есть не существует двух таких индексов $$$i, j$$$ ($$$i \ne j$$$), что $$$b_i = b_j$$$ и $$$g_i = g_j$$$ одновременно;
3. не существует такой пары, что цвет костюма мужчины равен цвету костюма женщины в этой паре, то есть $$$b_i \ne g_i$$$ для всех $$$i$$$;
4. для каждых двух последовательных (соседних) пар цвета костюмов мужчин и цвета костюмов женщин отличаются, то есть для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$ должны выполняться условия $$$b_i \ne b_{i + 1}$$$ и $$$g_i \ne g_{i + 1}$$$.

Посмотрим на примеры хороших и плохих выборов цветов (для $$$n=4$$$ и $$$k=3$$$, мужчина — первый в паре, а женщина — вторая):

Плохие выборы цветов:

• $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(1, 2)$$$ — противоречие со вторым условием (есть одинаковые пары);
• $$$(2, 3)$$$, $$$(1, 1)$$$, $$$(3, 2)$$$, $$$(1, 3)$$$ — противоречие с третьим условием (существует пара в костюмах одинаковых цветов);
• $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 1)$$$ — противоречие с четвертым условием (есть две последовательные пары такие, что цвета костюмов мужчин/женщин совпадают).

Хорошие выборы цветов:

• $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(1, 3)$$$, $$$(3, 1)$$$;
• $$$(1, 2)$$$, $$$(3, 1)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$;
• $$$(3, 1)$$$, $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$.

Вам необходимо найти любой подходящий выбор цветов или сказать, что таких выборов не существует.