Background

During the summer vacation, the school does not provide lunch, so Gnar has to order takeout with his friends.

The awkward part is that when the takeout arrives quickly, no one is willing to go to the school gate to pick it up, given the scorching outdoor temperature of $35\degree\!\text{C}$! At this point, Gnar comes up with a great idea: "I've prepared a piece of paper for each person, one of which is marked. Let's draw lots to decide who gets the marked one and goes to pick up the takeout!"

As a result, Gnar ends up fetching the takeout for six consecutive days.

This makes him feel不服又委屈: "Let's change the rules! Each person prepares three pieces of paper, five of which are marked. Each person draws three pieces, and the one with the most marked pieces goes to pick up the takeout!"

Gnar nervously unfolds the papers in his hand and sees two marked ones. Just as everyone is about to burst into laughter at his bad luck, someone slowly raises three pieces of paper and says, "I also got two marked ones..."

Problem Description

Curious, Gnar wants to study the number of people who usually get the most marked pieces. He prepares $m$ pieces of paper for each of the $n$ participants, totaling $nm$ pieces, of which exactly $k$ are marked in advance. Then, each person draws $m$ pieces from the uniformly shuffled papers.

A person gets the most marked pieces if and only if no one else gets more marked pieces than them. Help Gnar determine if it is possible for exactly $\boldsymbol{p}$ people to get the most marked pieces. Since Gnar likes to get to the bottom of things, if it is possible, you also need to construct how many marked and unmarked pieces each person draws.

Formally, suppose the $i$-th person draws $x_i$ marked pieces and $y_i$ unmarked pieces. Your construction should satisfy:

• $x_i, y_i \ge 0$, $x_i + y_i = m$.
• $\displaystyle \sum_{i = 1}^{n} x_i = k$.
• There are exactly $\boldsymbol{p}$ distinct $j$ such that $\displaystyle x_j = \max_{i = 1}^{n} \{x_i\}$.

Input Format

Input consists of four integers $n, m, k, p$, as described in the problem statement.

Output Format

The first line should output YES or NO (case-insensitive, e.g., yEs / No are acceptable) to indicate whether it is possible for exactly $p$ people to get the most marked pieces.

If the first line outputs YES, the next $n$ lines should each output $x_i, y_i$, representing the number of marked and unmarked pieces each person draws.

Since multiple answers may be possible, this problem uses a Special Judge, and any construction that meets the requirements in the problem statement is considered correct.

Sample Input and Output

Sample Input #1

3 3 5 2

Sample Output #1

YES
2 1
2 1
1 2

Sample Input #2

3 3 3 2

Sample Output #2

NO

Sample Input #3

3 3 5 3

Sample Output #3

NO

Notes/Hints

[Sample Explanation #1]

This sample provides a construction that satisfies the conditions described in the problem.

[Sample Explanation #2]

No matter how the marked pieces are distributed, there are only three possible scenarios from highest to lowest: $\{3,0,0\}$, $\{2,1,0\}$, $\{1,1,1\}$, corresponding to the number of people with the most marked pieces being $1$, $1$, $3$ respectively. Therefore, it is impossible to construct a scenario where $p = 2$.

[Data Range and Constraints]

This problem is group-tested. You must pass all test cases in a Subtask to earn points for that 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): No additional constraints.

For all data, it is guaranteed that $1 \le p \le n \le 10^5$, $1 \le m \le 10^9$, $0 \le k \le$.

见题面 Input 部分

见题面 Output 部分