You have $k+1$ marbles that are identical in shape and mass. Among these, $k$ marbles are ordinary, and $1$ marble is a magic marble. You intend to find the magic marble to enter the magic castle.

Although there is no way to distinguish the magic marble from ordinary marbles with the naked eye, there are $M$ ($M \ge 2$) bags that can be used to identify the magic marble. The bags are numbered from $0$ to $M-1$.

The method for using the bags to find the magic marble is as follows:

1. Distribute all the marbles you have into the $M$ bags.
   • No marble should be left outside of the bags.
   • It is allowed to have empty bags that contain no marbles.
   • Only marbles can be placed inside the bags; you cannot place other bags inside a bag.
2. Cast a spell.
3. Immediately after casting the spell:
   • All marbles in bags that do not contain the magic marble are destroyed.
   • Marbles in the bag containing the magic marble are protected by the magic marble and are not destroyed. However, you must handle the side effects caused by the spell, which incurs a cost. If the magic marble was in bag $i$, and there were $j$ marbles in bag $i$, the cost incurred is $A[i] \times j + B[i]$ (where $A[i] \ge 0, B[i] \ge 1$).

Since the magic marble is never destroyed, you can find the magic marble by repeating the above process until only one magic marble remains.

You want to establish a strategy for distributing the marbles into the bags to minimize the cost of finding the magic marble in the worst case. That is, for any of the $k+1$ marbles being the magic marble, you want to find the minimum $w$ such that the magic marble can be found with a total cost of at most $w$.

Write a function that solves this problem for all $k$ from $0$ to $N-1$.

Implementation Details

You must implement the following function:

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

• $N$: The maximum number of marbles.
• $A, B$: Arrays of length $M$. For all $i$ ($0 \le i \le M-1$), if the magic marble is in bag $i$ and there are $j$ marbles in bag $i$, the cost incurred is $A[i] \times j + B[i]$.
• This function must return an array $C$ of length $N$. For all $k$ ($0 \le k \le N-1$), $C[k]$ is the minimum cost (in units of currency) to find the magic marble in the worst case when there are $k$ ordinary marbles and $1$ magic marble.

You must not execute any input/output functions in any part of your submitted source code.

Examples

Input 1

3 2
1 2
3 1

Output 1

0 4 8

Note

When $k = 0$, the only marble you have is the magic marble, so you can find it with a cost of $0$.

When $k = 1$, you can adopt a strategy of putting one marble in each of the two bags. If the magic marble was in bag $0$, the cost is $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$, and if it was in bag $1$, the cost is $A[1] \times 2 + B[1] = 3 \times 1 + 1 = 4$. Therefore, the worst-case cost is $4$.

When $k = 2$, you can adopt the following strategy. For convenience, let the three marbles be $X, Y, Z$. Put $X, Z$ in bag $0$ and $Y$ in bag $1$, then cast the spell. If the magic marble is in bag $0$: The cost is $A[0] \times 2 + B[0] = 1 \times 2 + 2 = 4$, and only $X, Z$ remain. Now, put $Z$ in bag $0$ and $X$ in bag $1$, then cast the spell. If the magic marble is in bag $0$: The cost is $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$, and only $Z$ remains. If the magic marble is in bag $1$: The cost is $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$, and only $X$ remains. * If the magic marble is in bag $1$: The cost is $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$, and only $Y$ remains.

In this strategy, if $X$ is the magic marble, the total cost is $4 + 4 = 8$; if $Y$ is the magic marble, the total cost is $4$; if $Z$ is the magic marble, the total cost is $4 + 3 = 7$. Therefore, the worst-case cost is $8$.

Input 2

13 2
1 2
3 1

Output 2

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

Input 3

12 3
5 1
3 4
0 6

Output 3

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

Constraints

• $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$

Subtasks

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. No additional constraints