Description:
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.
Input Format:
The only line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n, k \le 2 \cdot 10^5$$$) — the number of pairs and the number of colors.
Output Format:
If it is impossible to find any suitable colors choosing, print "NO".
Otherwise print "YES" and then the colors of the costumes of pairs in the next $$$n$$$ lines. The $$$i$$$-th line should contain two integers $$$b_i$$$ and $$$g_i$$$ — colors of costumes of man and woman in the $$$i$$$-th pair, respectively.
You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.
Note:
None