你有 $k+1$ 顆形狀和質量完全相同的彈珠，其中 $k$ 顆是普通彈珠，另一顆是魔法彈珠。你想找到魔法彈珠，以進入魔法城堡。

雖然無法用肉眼區分魔法彈珠和普通彈珠，但你有 $M$ 個可用於尋找魔法彈珠的袋子（$M \ge 2$），編號為 $0$ 到 $M-1$。

使用袋子尋找魔法彈珠的方法如下。

1. 將你擁有的所有彈珠分裝到 $M$ 個袋子中。

   • 每顆彈珠都必須放入某個袋子。
   • 可以有不裝彈珠的空袋子。
   • 袋子裡只能裝彈珠，不能裝其他袋子。

2. 念咒語。

3. 念完咒語後立刻發生以下事情：

   • 不含魔法彈珠的袋子中的所有彈珠都會消失。
   • 含有魔法彈珠的袋子中的彈珠受到保護，不會消失。但是，處理咒語的副作用需要花錢。如果魔法彈珠在 $i$ 號袋子中，該袋子裝有 $j$ 顆彈珠，則花費 $A[i] \times j+B[i]$ 韓元（$A[i] \ge 0$，$B[i] \ge 1$）。

魔法彈珠永遠不會消失，因此重複上述過程直到只剩一顆彈珠，就能找到魔法彈珠。

你希望制定將彈珠分裝到袋子中的策略，使最壞情況下找到魔法彈珠的總花費最小。也就是說，求最小的 $w$，使得無論 $k+1$ 顆彈珠中哪顆是魔法彈珠，都能花費不超過 $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$），如果魔法彈珠在裝有 $j$ 顆彈珠的 $i$ 號袋子中，則花費 $A[i] \times j+B[i]$ 韓元。
• 函式應回傳長度為 $N$ 的陣列 $C$。對於所有 $k$（$0 \le k \le N-1$），$C[k]$ 表示有 $k$ 顆普通彈珠和一顆魔法彈珠時，在最壞情況下找到魔法彈珠所需的最小花費，單位為韓元。

提交的原始碼中任何部分都不得執行輸入輸出函式。

範例

範例 1

考慮以下情況： $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

評測程式按如下方式呼叫函式。

find_minimum_costs(3, {1, 3}, {2, 1})

當 $k=0$ 時，唯一的彈珠就是魔法彈珠，因此花費 $0$ 韓元即可找到它。

當 $k=1$ 時，可以在每個袋子中放一顆彈珠。若魔法彈珠在 $0$ 號袋子中，花費為 $A[0] \times 1+B[0]=1 \times 1+2=3$ 韓元；若在 $1$ 號袋子中，花費為 $A[1] \times 2+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$ 韓元。

函式應回傳 $[0,4,8]$.

範例 2

考慮以下情況： $N=13$, $M=2$, $A=[1,3]$, $B=[2,1]$.

評測程式按如下方式呼叫函式。

find_minimum_costs(13, {1, 3}, {2, 1})

函式應回傳 $[0,4,8,11,13,17,18,20,24,25,27,29,30]$.

範例 3

考慮以下情況： $N=12$, $M=3$, $A=[5,3,0]$, $B=[1,4,6]$.

評測程式按如下方式呼叫函式。

find_minimum_costs(12, {5, 3, 0}, {1, 4, 6})

函式應回傳 $[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$ (對於所有 $0 \le i \le M-1$).
• $1 \le B[i] \le 10^9$ (對於所有 $0 \le i \le M-1$).

子任務

1. ($3$ 分) $A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$.
2. ($4$ 分) $N \le 5\,000$, $M=2$.
3. ($7$ 分) $M=2$.
4. ($12$ 分) $A[i]=0$, $B[i] \le 1\,000$ (對於所有 $0 \le i \le M-1$).
5. ($25$ 分) $N \le 10\,000$, $M \le 10$.
6. ($17$ 分) $M \le 100$.
7. ($32$ 分) 沒有額外限制。

範例評測程式

範例評測程式的輸入格式如下。

• 行 $1$: $N$ $M$
• 行 $2+i$ ($0 \le i \le M-1$): $A[i]$ $B[i]$

範例評測程式的輸出格式如下。

• 行 $1+k$ ($0 \le k \le N-1$): $C[k]$