P7107.md

天选之人

题目描述

好奇的 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，只要构造符合题面中的要求均视为正确。

样例 #1

样例输入 #1

3 3 5 2

样例输出 #1

YES
2 1
2 1
1 2

样例 #2

样例输入 #2

3 3 3 2

样例输出 #2

NO

样例 #3

样例输入 #3

3 3 5 3

样例输出 #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$。