Construct a Sequence with a Given Count of Valid Pair Sums

You are given three integers n, p and q. Your task is to construct a sequence of n integers a₁, a₂, …, a_n such that:

• For all 1 ≤ i ≤ n, 1 ≤ a_i ≤ 10⁷ and a_i is an integer.
• If we define a pair (i, j) (with i < j) to be valid when a_i + a_j ≤ q, then there must be exactly p valid pairs among the total n(n-1)/2 pairs.

In other words, out of all unordered pairs (i,j) (i < j), exactly p of the pair sums must be ≤ q.

If multiple solutions exist, you only need to output one of them.

Note on Constraints and Special Cases:

• If p = 0 you may choose all numbers to be large (for example, q+1) so that no pair sum is ≤ q.
• If p = n(n-1)/2 then you should output all 1’s.
• It is guaranteed that the input will be such that a valid sequence exists. (In some cases when q is very small—for example, 2 or 3—the only possible valid sequences are very constrained.)

Idea of a Construction (for the case q ≥ 4):

Assume q ≥ 4. One can show that by properly choosing some numbers in the sequence you can control the number of valid pairs. For instance, if several numbers are set to 1 then any pair among them is valid (since 1+1 =2 ≤ q). On the other hand, if some numbers are made larger (for example, using a value 2 or even q+1) then many pairs become invalid. A useful construction is as follows (this construction works when q ≥ 4):

1. If p = n(n-1)/2, output a_i = 1 for all i.
2. If p = 0, output a_i = q+1 for all i.
3. Otherwise, pick an integer k (with 1 ≤ k ≤ n-1) such that
   C(k,2) ≤ p ≤ C(k,2) + k, where C(k,2) = k*(k-1)/2.
4. Let r = p - C(k,2) (so 0 ≤ r ≤ k).
5. Then construct the sequence as follows (for q ≥ 4):
   • For the first group of k numbers, assign a split:
     • Set the first r numbers to 1.
     • Set the remaining k - r numbers to 2. (Notice that 1+2 = 3 ≤ q and 2+2 = 4 ≤ q.)
   • Next, set one extra number (position k+1) to q-1 if r > 0 or to q if r = 0. With this extra element, only those numbers in the group set to 1 will pair with it to form a valid sum (since 1+(q-1) = q ≤ q, while 2+(q-1) = q+1 > q).
   • Set the remaining n - (k+1) numbers to q+1 so that they do not contribute any valid pairs.
6. This construction guarantees that the number of valid pairs is exactly:
   (valid pairs within the first group) C(k,2) + (pairs between the extra element and those equal to 1) = C(k,2) + r = p.

For q = 2 or q = 3, the range of possible sequences is more limited. For example, when q = 2 the only possibility for a valid pair is when both numbers equal 1. For q = 3 a valid pair can be achieved by (1,1) or (1,2) (since 1+2 = 3), while (2,2) is invalid (2+2 = 4 > 3). In these cases one may use a modified construction. For instance, when q = 3 and p is neither 0 nor n(n-1)/2, one valid solution is to have exactly m copies of 1 and n-m copies of 2, where m is chosen so that the total number of valid pairs (which is C(m,2) + m*(n-m)) equals p.

Your solution should implement all these cases.

inputFormat

The input consists of a single line containing three integers n, p and q separated by spaces.

outputFormat

Output one line containing n integers a₁, a₂, …, a_n separated by spaces, which form a valid sequence satisfying the conditions.

sample

5 3 10

1 1 9 11 11