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 the delivery arrives quickly, but no one wants to go to the school gate to pick it up, because it is $35\degree\!\text{C}$ outside! At this moment, Gnar comes up with an idea: “I rolled a paper ball for each person. One of them has a mark on it. Let’s draw lots. Whoever draws the marked one goes to pick it up!”

So Gnar ended up picking up takeout for six days in a row.

He feels both upset and wronged: “Change the rules! Each person prepares three paper balls. Five of them are marked. Everyone draws three. Whoever has the most marks goes to pick it up!”

Gnar nervously unfolds the paper balls in his hand, and two marks are right there in front of him. Just as everyone is about to laugh at his bad luck, someone slowly raises three paper slips and says, “I also drew two marks…”

Problem Description

Curious, Gnar wants to study, in the general case, how many people can end up with the most marks. He prepares $m$ rolled paper balls for each of the $n$ participants, for a total of $nm$ paper balls, among which exactly $k$ are marked in advance. Then, after the paper balls are uniformly shuffled, each person draws $m$ paper balls.

A person has the most marks if and only if no one else has more marks than them. Please help Gnar determine whether it is possible that exactly $\boldsymbol{p}$ people draw the most marks. Since Gnar likes to get to the bottom of things, if it is possible, you also need to construct how many marked and unmarked paper balls each person draws.

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

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

Input Format

Input four integers $n, m, k, p$, whose meanings are described above.

Output Format

Output YES or NO in the first line (case-insensitive, e.g., yEs / No are both accepted), indicating whether it is possible that exactly $p$ people draw the most marks.

If the first line is YES, then output $n$ lines, each containing $x_i, y_i$, representing the numbers of marked and unmarked paper balls drawn by each person.

Since the answer may not be unique, this problem uses a Special Judge. Any construction that satisfies the requirements in the statement will be accepted.

3 3 5 2

YES
2 1
2 1
1 2

3 3 3 2

NO

3 3 5 3

NO

Hint

[Sample Explanation #1]

The sample provides one construction that satisfies the conditions.

[Sample Explanation #2]

No matter what, there are only three possible distributions of marks from high to low: $\{3,0,0\}$, $\{2,1,0\}$, $\{1,1,1\}$. The corresponding numbers of people with the most marks are $1$, $1$, and $3$. Therefore, it is impossible to construct a solution with $p = 2$.

[Constraints and Conventions]

This problem uses bundled testdata. You must pass all test points in a Subtask to receive the score 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 special constraints.

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

Translated by ChatGPT 5