Construct a Sequence with Exactly k Good Intervals

We are given two integers n and k. A sequence (a_1,a_2,\dots,a_n) of integers (each in the range (-10^{12} \le a_i < 10^{12})) is said to have a good interval ([l,r]) (with (1 \le l \le r \le n)) if for every index (t) with (l \le t \le r) the partial sum [ \sum_{i=l}^{t} a_i > 0, ] holds. (Note that an interval of length 1, i.e. where (l=r), is considered as an interval.)

Your task is to construct a sequence of length n satisfying the following conditions:

1. The number of good intervals in the sequence is exactly k.
2. The weighted sum [ \sum_{i=1}^n (n-i+1)\times a_i = \frac{n(n+1)}{2}, ] holds.
3. Each (a_i) is an integer satisfying (-10^{12} \le a_i < 10^{12}).

If no such sequence exists, output a sequence of n zeros.

Note: It can be shown that when n > 1 the number of good intervals for the constant sequence (a_i\equiv 1) is [ \frac{n(n+1)}{2}, ] and by making a small change at the beginning of the sequence we can "ruin" some of the intervals. In our construction we will use the following idea (which works when \n(n-1)/2 \le k \le n(n+1)/2):

Let (T = \frac{n(n+1)}{2}). If we define (X = T - k) (so (0 \le X \le n) for a valid solution when (n>1); for (n=1) the only possibility is (k=1)), then we take

• (a_1 = 1 - X),
• (a_i = 1) for (2 \le i \le n-1) (if any),
• (a_n = 1 + n\times X).

One may check that the weighted sum is preserved, and the only effect on the count of good intervals is on those intervals starting at index 1. In fact, for an interval starting at 1 the partial sums are [ s_t = (1-X) + (t-1)\quad (1 \le t \le n), ] so the condition (s_t > 0) holds if and only if (t > X). Hence, the number of good intervals starting at 1 is exactly (n - X) (or 0 if (X \ge n)). All other intervals (starting at indices 2 through (n)) remain unaffected from the base case (where they contribute (\sum_{i=2}^n (n-i+1) = n(n-1)/2) intervals). Consequently, the total number of good intervals becomes [ (n - X) + \frac{n(n-1)}{2} = T - X = k. ]

If the given k does not lie in the admissible range (that is, if for (n=1) (k\neq1) or for (n>1) if (k < \frac{n(n-1)}{2}) or (k > \frac{n(n+1)}{2})), then it is impossible to build such a sequence – in that case, output a sequence of n zeros.

The input consists of two space‐separated integers n and k. The output should be the constructed sequence of n integers separated by spaces (or the all-zero sequence if no solution exists).

inputFormat

The input consists of one line with two space‐separated integers n and k:

• n (the length of the sequence, 1 ≤ n ≤ 10⁵ for example)
• k (the desired number of good intervals)

outputFormat

Output one line containing n integers a₁, a₂, …, a_n separated by spaces, representing the sequence satisfying the conditions. If no valid sequence exists, output n zeros.

sample

1 1

1

</p>