Você tem $k+1$ bolinhas com forma e massa idênticas: $k$ comuns e uma mágica. Você quer encontrar a bolinha mágica para entrar no castelo mágico.

Não é possível distingui-la visualmente, mas há $M$ sacolas ($M \ge 2$) que podem ajudar a encontrá-la, numeradas de $0$ a $M-1$.

As sacolas podem ser usadas da seguinte forma.

1. Distribua todas as suas bolinhas entre as $M$ sacolas.

   • Toda bolinha deve ser colocada em alguma sacola.
   • Pode haver sacolas vazias.
   • As sacolas só podem conter bolinhas, não outras sacolas.

2. Recite um feitiço.

3. Imediatamente após o feitiço:

   • Todas as bolinhas nas sacolas sem a bolinha mágica desaparecem.
   • As bolinhas na sacola com a bolinha mágica são protegidas e não desaparecem. Porém, lidar com os efeitos colaterais do feitiço custa dinheiro. Se a bolinha mágica estava na sacola $i$, contendo $j$ bolinhas, o custo é $A[i] \times j+B[i]$ wons ($A[i] \ge 0$, $B[i] \ge 1$).

A bolinha mágica nunca desaparece; portanto, repetir o processo até restar uma única bolinha permite encontrá-la.

Escolha uma estratégia de distribuição que minimize o custo total no pior caso. Isto é, encontre o menor $w$ que permita encontrar a bolinha mágica gastando no máximo $w$ wons, qualquer que seja a mágica entre as $k+1$ bolinhas.

Escreva uma função que resolva o problema para todo $k$ de $0$ a $N-1$.

Detalhes de implementação

Implemente a função a seguir.

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

• $N$: quantidade máxima de bolinhas.
• $A,B$: vetores de tamanho $M$. Para todo $i$ ($0 \le i \le M-1$), se a bolinha mágica estiver na sacola $i$ contendo $j$ bolinhas, o custo será $A[i] \times j+B[i]$ wons.
• Retorne um vetor $C$ de tamanho $N$. Para todo $k$ ($0 \le k \le N-1$), $C[k]$ é o menor custo no pior caso, em wons, de encontrar a bolinha mágica entre $k$ comuns e uma mágica.

Nenhuma parte do código enviado deve executar funções de entrada/saída.

Exemplos

Exemplos 1

Considere o caso $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

O avaliador chama a função assim.

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

Para $k=0$, a única bolinha é mágica, portanto o custo para encontrá-la é $0$ wons.

Para $k=1$, coloque uma bolinha em cada sacola. Se a mágica estiver na sacola $0$, o custo será $A[0] \times 1+B[0]=1 \times 1+2=3$ wons; se estiver na $1$, será $A[1] \times 2+B[1]=3 \times 1+1=4$ wons. O pior custo é $4$ wons.

Para $k=2$, use a estratégia abaixo, chamando as bolinhas de $X,Y,Z$.

• Coloque $X,Z$ na sacola $0$ e $Y$ na $1$, e recite o feitiço.

  • Se a mágica estiver na sacola $0$, o custo será $A[0] \times 2+B[0]=1 \times 2+2=4$ wons e restarão apenas $X,Z$. Coloque então $Z$ na sacola $0$ e $X$ na $1$, e recite o feitiço.

    • Se a mágica estiver na sacola $0$, o custo será $A[0] \times 1+B[0]=1 \times 1+2=3$ wons e restará apenas $Z$.

    • Se a mágica estiver na sacola $1$, o custo será $A[1] \times 1+B[1]=3 \times 1+1=4$ wons e restará apenas $X$.

  • Se a mágica estiver na sacola $1$, o custo será $A[1] \times 1+B[1]=3 \times 1+1=4$ wons e restará apenas $Y$.

Com essa estratégia, o custo total é $4+4=8$ wons se $X$ for mágica, $4$ se for $Y$, e $4+3=7$ se for $Z$. Assim, o pior custo é $8$ wons.

A função deve retornar $[0,4,8]$.

Exemplos 2

Considere o caso $N=13$, $M=2$, $A=[1,3]$, $B=[2,1]$.

O avaliador chama a função assim.

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

A função deve retornar $[0,4,8,11,13,17,18,20,24,25,27,29,30]$.

Exemplos 3

Considere o caso $N=12$, $M=3$, $A=[5,3,0]$, $B=[1,4,6]$.

O avaliador chama a função assim.

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

A função deve retornar $[0,6,7,12,13,16,17,18,19,20,22,23]$.

Restrições

• $2 \le N \le 1\,000\,000$
• $2 \le M \le 100\,000$
• $0 \le A[i] \le 10^9$ (para todo $0 \le i \le M-1$).
• $1 \le B[i] \le 10^9$ (para todo $0 \le i \le M-1$).

Subtarefas

1. ($3$ pontos) $A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$.
2. ($4$ pontos) $N \le 5\,000$, $M=2$.
3. ($7$ pontos) $M=2$.
4. ($12$ pontos) $A[i]=0$, $B[i] \le 1\,000$ (para todo $0 \le i \le M-1$).
5. ($25$ pontos) $N \le 10\,000$, $M \le 10$.
6. ($17$ pontos) $M \le 100$.
7. ($32$ pontos) Sem restrições adicionais.

Avaliador de exemplo

O formato de entrada do avaliador de exemplo é o seguinte.

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

O formato de saída do avaliador de exemplo é o seguinte.

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