Problem Description

Given three integers $n, p, q$, you need to construct a sequence $a$ of length $n$ such that:

• $\forall 1 \leq i \leq n: 1 \leq a_i \leq 10^7, a_i \in \mathbb{Z}$；

• $(\sum\limits_{1 \leq i < j \leq n} [a_i + a_j \leq q]) = p$。

In plain words, each number is a positive integer within $[1, 10^7]$, and among the $\dfrac{n(n-1)}{2}$ pair sums formed by choosing two numbers from different positions (order does not matter), there are exactly $p$ sums that are not greater than $q$. You only need to output one valid construction.

Input Format

One line with three integers $n, p, q$.

Output Format

One line with $n$ numbers, representing the constructed sequence.

4 2 5

1 3 4 15

Hint

Constraints

For $100\%$ of the testdata, $4 \leq n \leq 10^6$, $0 \leq p \leq \dfrac{n(n-1)}{2}$, $4 \leq q \leq 10^7$.

Update 2024.7.1: According to this post, a set of hack testdata was added into subtask $2$, with a score of $0$ points.

Translated by ChatGPT 5