Marked Paper Ball Distribution

Curious Gnar is studying the scenario in which among n participants each drawing m paper balls, exactly k out of the total nm balls are pre-marked. After shuffling all the balls, every person draws exactly m balls. We call a person one who drew the maximum number of marked balls if no one else drew more marked balls than him. Gnar wonders: is it possible that exactly p persons achieve this maximum marked ball count?

If possible, you are required not only to determine the possibility, but also to construct a valid distribution. Formally, for each person i (1 ≤ i ≤ n), let x_i be the number of marked balls drawn and y_i be the number of unmarked balls drawn. 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 exist exactly p distinct indices \( j \) such that \( x_j = \max_{1 \le i \le n} \{x_i\} \).

If a valid distribution exists, output YES followed by n lines, each containing two integers: the number of marked balls and unmarked balls for that person. Otherwise, output NO.

Notes:

• The values n, m, k, and p are given in a single line separated by spaces.
• If p = n, then every person must have the same number of marked balls. In this case, a valid solution exists if and only if \( k \) is divisible by \( n \) and \( \frac{k}{n} \le m \).
• For p < n, we choose a candidate maximum marked count \( M \) (with \( 1 \le M \le m \)). We assign exactly p persons \( x_i = M \), and distribute the remaining \( k - pM \) marks among the other \( n-p \) persons such that each gets at most \( M-1 \) marks.

inputFormat

The input consists of a single line containing four integers n, m, k, and p:

• n (the number of people)
• m (the number of balls each person draws)
• k (the total number of pre-marked balls)
• p (the exact number of people who must tie for the maximum marks)

outputFormat

If a valid distribution exists, output YES on the first line, followed by n lines. The i-th of these lines should contain two integers \( x_i \) and \( y_i \) separated by a space, where:

• \( x_i \) is the number of marked balls for person i, and
• \( y_i = m - x_i \) is the number of unmarked balls for person i.

If no valid distribution exists, output a single line containing NO.

sample

3 5 10 2

YES
4 1
4 1
2 3