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.

Longest Increasing Path (Hard Version)

Examples