贝尔兰德国王组织舞会! $$$n$$$ 一对被邀请参加舞会,他们的编号从 $$$1$$$ 到 $$$n$$$。每对由一名男子和一名女子组成。每个舞者(无论是男性还是女性)都有一套单色服装。每个服装的颜色由从 $$$1$$$ 到 $$$k$$$(含)的整数表示。
设 $$$b_i$$$ 为第 $$$i$$$ 组中男士服装的颜色,$$$g_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. 不存在男装颜色与女装颜色相同的一对,即每 $$$i$$$ 都有 $$$b_i \ne g_i$$$ ;
4. 对于每两个连续(相邻)对,男士服装颜色和女士服装颜色都不同,即对于从 $$$1$$$ 到 $$$n-1$$$ 的每个 $$$i$$$,条件 $$$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)$$$.
您必须找到任何合适的颜色选择或说不存在合适的选择。
输入
输入的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n, k \le 2 \cdot 10^5$$$) — 对的数量和颜色的数量。
输出
如果无法找到合适的颜色选择,请打印“NO”。
否则打印“YES”,然后在接下来的 $$$n$$$ 行中打印成对服装的颜色。第 $$$i$$$ 行应包含两个整数 $$$b_i$$$ 和 $$$g_i$$$ — 分别是第 $$$i$$$ 对中男人和女人服装的颜色。
您可以以任何大小写(大写或小写)打印每个字母。例如,“Yes”、“no”和“yES”都是可接受的。
示例
输入 #1
4 3
输出 #1
YES 3 1 1 3 3 2 2 3
输入 #2
10 4
输出 #2
YES 2 1 1 3 4 2 3 4 4 3 3 2 2 4 4 1 1 4 3 1
输入 #3
13 4
输出 #3
NO