I2. 最长递增路径（困难版本）
每次测试时间限制：$2$ 秒
每次测试内存限制：$256$ 兆字节

这是问题的困难版本。与简单版本的区别在于，该版本的第二个测试点中 $n = 300\,000$。本题不允许使用黑客攻击。

我们称一个整数序列 $a_1, a_2, \ldots, a_n$ 为 距离凸，如果

$$|a_{i} - a_{i-1}| < |a_{i+1} - a_{i}| \quad\text{对于所有}\quad 1 < i < n $$

换句话说，依次跳转到 $a_1, a_2, \ldots, a_n$ 时，每一步的跳跃长度都严格大于上一步。

给定两个整数 $n$ 和 $m$。请构造一个长度为 $n$ 的 距离凸 序列 $a$，且序列中不同的数值个数 不超过 $m$。
就跳跃过程而言，这意味着你需要在访问最多 $m$ 个不同点的过程中，完成 $n-1$ 次跳跃，且跳跃长度严格递增。
所有 $a_i$ 必须满足 $-10^{18} \le a_i \le 10^{18}$。

---

输入

输入只有一行，包含两个整数 $n$ 和 $m$。

本题只有两种测试数据：

• $n = 8$，$m = 6$；
• $n = 300\,000$，$m = 15\,000$。

两种测试都保证有解。
本题不允许使用黑客攻击。

---

输出

输出一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示构造出的距离凸序列。
序列中不同数值的个数必须不超过 $m$，且所有 $a_i$ 应在 $[-10^{18}, 10^{18}]$ 范围内。

如果有多解，输出任意一组即可。

---

示例

输入：

8 6

输出：

1 1 3 6 10 3 11 1

注释：
序列 $[1, 1, 3, 6, 10, 3, 11, 1]$ 长度为 $n=8$，包含 $5$ 个不同的值，不超过 $m=6$。
相邻差的绝对值为 $0, 2, 3, 4, 7, 8, 10$，严格递增。
$[1, 1, 2, 4, 8, 16, 32, 1]$ 也是一个有效答案。