This is the hard version of the problem. The difference between the versions is that in this version the second test is $n=300\,000$. Hacks are not allowed in this problem.

Let's call an integer sequence $a_1, a_2, \ldots, a_n$ distance-convex if $|a_{i} - a_{i-1}| \lt |a_{i+1} - a_{i}|$ for every $1 \lt i \lt n$. In other words, if you jump through the points $a_1, a_2, \ldots, a_n$ in this order, each next jump is strictly longer than the previous one.

You are given two integers $n$ and $m$. Find a distance-convex sequence $a$ of length $n$ that contains at most $m$ distinct values. In terms of the jump sequence, that would mean that you need to make $(n-1)$ jumps of increasing lengths while visiting at most $m$ distinct points. $-10^{18} \le a_i \le 10^{18}$ should hold for all $1 \le i \le n$.

Input

Input consists of two integers $n$ and $m$.

There are only 2 tests for this problem.

• $n = 8$, $m = 6$;
• $n = 300\,000$, $m = 15\,000$.

It is guaranteed that an answer exists for both tests.

Hacks are not allowed in this problem.

Output

Print a distance-convex sequence $a_1, a_2, \ldots, a_n$ that contains at most $m$ distinct values. $-10^{18} \le a_i \le 10^{18}$ should hold for all $1 \le i \le n$.

If there are multiple solutions, print any of them.

Note

The sequence $[1, 1, 3, 6, 10, 3, 11, 1]$ has length $n=8$ and contains $5$ different values, which is less than or equal to $m=6$. The differences between consecutive values are $0,2,3,4,7,8,10$, a strictly increasing sequence.

$[1, 1, 2, 4, 8, 16, 32, 1]$ would be another valid answer.