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