你拥有 $k+1$ 个形状和质量完全相同的球。其中 $k$ 个是普通球，1 个是魔法球。你打算找到魔法球并进入魔法城堡。

虽然肉眼无法区分魔法球和普通球，但有 $M$ ($M \ge 2$) 个口袋可用于寻找魔法球。口袋编号从 0 到 $M-1$。

利用口袋寻找魔法球的方法如下：

1. 将所有拥有的球分配到 $M$ 个口袋中。
   • 不允许有球不放入任何口袋。
   • 可以有不装球的空口袋。
   • 口袋里只能装球，不能装其他口袋。
2. 念咒语。
3. 念完咒语后：
   • 没有装魔法球的口袋里的球全部消失。
   • 装有魔法球的口袋里的球受到魔法球的保护，不会消失。但是，需要处理咒语产生的副作用，此过程会产生费用。如果魔法球在 $i$ 号口袋中，且 $i$ 号口袋里装有 $j$ 个球，则花费 $A[i] \times j + B[i]$ 元 ($A[i] \ge 0, B[i] \ge 1$)。

由于魔法球永远不会消失，重复上述过程直到只剩 1 个魔法球，即可找到魔法球。

你需要制定将球分配到口袋的策略，以最小化在最坏情况下找到魔法球所需的费用。即，对于 $k+1$ 个球中的任意一个球是魔法球的情况，总花费不超过 $w$ 元，求出最小的 $w$。

请编写一个函数，解决 $0$ 到 $N-1$ 之间所有 $k$ 的问题。

实现细节

你需要实现以下函数：

vector<long long> find_minimum_costs(int N, vector<int> A, vector<int> B)

• $N$: 球的最大数量。
• $A, B$: 长度为 $M$ 的数组。对于所有 $i$ ($0 \le i \le M-1$)，如果魔法球在 $i$ 号口袋中，且 $i$ 号口袋里装有 $j$ 个球，则花费 $A[i] \times j + B[i]$ 元。
• 该函数应返回一个长度为 $N$ 的数组 $C$。对于所有 $k$ ($0 \le k \le N-1$)，$C[k]$ 是在有 $k$ 个普通球和 1 个魔法球时，在最坏情况下找到魔法球所需的最小费用（单位：元）。

提交的源代码中不得执行任何输入输出函数。

样例

输入格式 1

3 2
1 2
3 1

输出格式 1

0 4 8

说明

当 $k=0$ 时，唯一的球就是魔法球，因此花费 0 元即可找到。

当 $k=1$ 时，可以制定将球分别放入两个口袋的策略。如果魔法球在 0 号口袋，花费 $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$ 元；如果在 1 号口袋，花费 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元。因此，最坏情况下花费 4 元。

当 $k=2$ 时，可以制定如下策略。为方便起见，将三个球称为 X, Y, Z。

• 将 X, Z 放入 0 号口袋，将 Y 放入 1 号口袋，然后念咒语。
  • 如果魔法球在 0 号口袋：花费 $A[0] \times 2 + B[0] = 1 \times 2 + 2 = 4$ 元，只剩下 X, Z。现在将 Z 放入 0 号口袋，将 X 放入 1 号口袋，然后念咒语。
    • 如果魔法球在 0 号口袋：花费 $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$ 元，只剩下 Z。
    • 如果魔法球在 1 号口袋：花费 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元，只剩下 X。
  • 如果魔法球在 1 号口袋：花费 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元，只剩下 Y。

在此策略中，如果 X 是魔法球，总花费 $4 + 4 = 8$ 元；如果 Y 是魔法球，总花费 4 元；如果 Z 是魔法球，总花费 $4 + 3 = 7$ 元。因此，最坏情况下花费 8 元。

输入格式 2

13 2
1 2
3 1

输出格式 2

0 4 8 11 13 17 18 20 24 25 27 29 30

输入格式 3

12 3
5 1
3 4
0 6

输出格式 3

0 6 7 12 13 16 17 18 19 20 22 23

数据范围

• $2 \le N \le 1\,000\,000$
• $2 \le M \le 100\,000$
• $0 \le A[i] \le 10^9$
• $1 \le B[i] \le 10^9$

子任务

1. $A[0] = A[1] = \dots = A[M-1], B[0] = B[1] = \dots = B[M-1]$
2. $N \le 5\,000, M = 2$
3. $M = 2$
4. $A[i] = 0, B[i] \le 1\,000$
5. $N \le 10\,000, M \le 10$
6. $M \le 100$
7. 无额外限制