You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

暑假期间，学校不提供午餐，Gnar 只好找伙计们一起点外卖。

尴尬的是，外卖很快送到却没人乐意去校门口拿，毕竟户外可是 $35\degree\!\text{C}$ 高温！此时 Gnar 想到了好主意：“我给一人捏了一张纸团，其中一张写有记号，不如我们抓阄决定，谁抽到带记号的谁去拿！”

于是 Gnar 连续拿了六天的外卖。

这可让他不服又委屈：“换个规则！一人准备三张纸团，五张有记号，每人抽三张，记号最多的去拿！”

Gnar 紧张地展开手中的纸团，两个记号赫然映在眼前。大伙们刚想放声大笑他的非酋运气，有人缓缓举起三张纸片说道：“我也抽到了两个记号……”

题目描述

好奇的 Gnar 想研究一般情况下抽到最多记号的人数。他给参与抓阄的 $n$ 人一人准备了 $m$ 张捏好的纸团，一共 $nm$ 张，其中恰好 $k$ 张提前写了记号。随后每个人在均匀打乱的纸团中各抽 $m$ 张。

一个人抽到最多的记号，当且仅当没有人抽到的记号比他还多。请你帮 Gnar 判断是否可能会恰好 $\boldsymbol{p}$ 个人抽到最多的记号。Gnar 喜欢追根问底，所以如果有可能，你还需构造每个人抽的纸团中分别有多少带记号、有多少不带记号。

形式化地，假设第 $i$ 个人抽到了 $x_i$ 张带记号的纸团和 $y_i$ 张不带记号的纸团，你的构造应满足：

• $x_i, y_i \ge 0$，$x_i + y_i = m$。
• $\displaystyle \sum_{i = 1}^{n} x_i = k$。
• 有且仅有 $\boldsymbol{p}$ 个互不相同的 $j$ 使 $\displaystyle x_j = \max_{i = 1}^{n} \{x_i\}$。

输入格式

输入四个整数 $n, m, k, p$，含义详见题目描述。

输出格式

第一行输出 YES 或 NO（不区分大小写，yEs / No 均可），表示是否会恰好 $p$ 个人抽到最多的记号。

如果第一行输出 YES，接下来 $n$ 行每行输出 $x_i, y_i$，表示每个人抽到带与不带记号的纸团个数。

因答案可能不唯一，本题采用 Special Judge，只要构造符合题面中的要求均视为正确。

3 3 5 2

YES
2 1
2 1
1 2

3 3 3 2

NO

3 3 5 3

NO

提示

【样例解释 #1】

样例给出了一种满足题述条件的构造。

【样例解释 #2】

不论如何，记号的分布从高到低只有三种情况：$\{3,0,0\}$，$\{2,1,0\}$，$\{1,1,1\}$，抽到最多记号的人数分别对应 $1$，$1$，$3$。因此无法构造 $p = 2$ 的方案。

---

【数据规模与约定】

本题采用捆绑测试。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。

• Subtask #1 (15 points)：$n,m \le 8$。
• Subtask #2 (15 points)：$n,m \le 100$。
• Subtask #3 (20 points)：$n,m \le 10^5$。
• Subtask #4 (10 points)：$p = 1$。
• Subtask #5 (40 points)：无特殊限制。

对于所有的数据，保证 $1 \le p \le n \le {10}^5$，$1 \le m \le {10}^9$，$0 \le k \le n m$。