题目背景

学校组织一场抽奖活动，同学们对抽签结果的公平性产生了好奇。

题目描述

有 $n$ 个人参加抽奖活动，每个人准备了 $m$ 个纸团，共 $nm$ 个纸团中有恰好 $k$ 个写了记号。所有纸团被打乱后，每个人各抽取 $m$ 个。

一个人抽到的记号数最多，当且仅当没有人比他抽到更多记号。

请你判断是否可能恰好 oldsymbol{p} 个人抽到最多的记号。如果可能，还需构造一种方案：对每个人 $i$，输出他抽到的记号数 $x_i$ 和非记号数 $y_i$。

形式化地，构造需满足：

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

输入格式

一行四个整数 $n, m, k, p$。

输出格式

如果不可能，输出一行 NO。

如果可能，第一行输出 YES，接下来 $n$ 行每行两个整数 $x_i, y_i$，表示第 $i$ 个人抽到的记号数和非记号数。如果有多组解，输出任意一组即可。

样例

3 3 5 2

YES
2 1
2 1
1 2

3 3 3 2

NO

3 3 5 3

NO

提示

本题答案不唯一，评测使用 Special Judge 校验输出是否合法。

样例解释 #1
样例给出了一种满足条件的构造。
样例解释 #2
不论如何分配，记号的分布只有三种情况：$\{3,0,0\}$，$\{2,1,0\}$，$\{1,1,1\}$，抽到最多记号的人数分别对应 $1$，$1$，$3$。因此无法构造 $p=2$ 的方案。

数据范围

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

对于所有数据，$0 \le p \le n \le 10^5$，$1 \le n$，$1 \le m \le 10^9$，$0 \le k \le nm$。