The king of Berland organizes a ball! $$$n$$$ pair are invited to the ball, they are numbered from $$$1$$$ to $$$n$$$. Each pair consists of one man and one woman. Each dancer (either man or woman) has a monochrome costume. The color of each costume is represented by an integer from $$$1$$$ to $$$k$$$, inclusive.

Let $$$b_i$$$ be the color of the man's costume and $$$g_i$$$ be the color of the woman's costume in the $$$i$$$-th pair. You have to choose a color for each dancer's costume (i.e. values $$$b_1, b_2, \dots, b_n$$$ and $$$g_1, g_2, \dots g_n$$$) in such a way that:

1. for every $$$i$$$: $$$b_i$$$ and $$$g_i$$$ are integers between $$$1$$$ and $$$k$$$, inclusive;
2. there are no two completely identical pairs, i.e. no two indices $$$i, j$$$ ($$$i \ne j$$$) such that $$$b_i = b_j$$$ and $$$g_i = g_j$$$ at the same time;
3. there is no pair such that the color of the man's costume is the same as the color of the woman's costume in this pair, i.e. $$$b_i \ne g_i$$$ for every $$$i$$$;
4. for each two consecutive (adjacent) pairs both man's costume colors and woman's costume colors differ, i.e. for every $$$i$$$ from $$$1$$$ to $$$n-1$$$ the conditions $$$b_i \ne b_{i + 1}$$$ and $$$g_i \ne g_{i + 1}$$$ hold.

Let's take a look at the examples of bad and good color choosing (for $$$n=4$$$ and $$$k=3$$$, man is the first in a pair and woman is the second):

Bad color choosing:

• $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(1, 2)$$$ — contradiction with the second rule (there are equal pairs);
• $$$(2, 3)$$$, $$$(1, 1)$$$, $$$(3, 2)$$$, $$$(1, 3)$$$ — contradiction with the third rule (there is a pair with costumes of the same color);
• $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 1)$$$ — contradiction with the fourth rule (there are two consecutive pairs such that colors of costumes of men/women are the same).

Good color choosing:

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

You have to find any suitable color choosing or say that no suitable choosing exists.