I2. Longest Increasing Path (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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}| < |a_{i+1} - a_{i}|$$$ for every $$$1 < i < 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$$$.InputInput 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.OutputPrint 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.ExampleInput8 6Output1 1 3 6 10 3 11 1
NoteThe 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.