Masz $k+1$ kulek o identycznym kształcie i masie: $k$ zwykłych i jedną magiczną. Chcesz znaleźć magiczną kulkę, aby wejść do magicznego zamku.

Nie można jej odróżnić wzrokiem, ale masz $M$ woreczków ($M \ge 2$), które pomogą ją znaleźć. Są ponumerowane od $0$ do $M-1$.

Woreczki można wykorzystać następująco.

1. Rozdziel wszystkie posiadane kulki między $M$ woreczków.

   • Każda kulka musi trafić do woreczka.
   • Woreczki mogą pozostać puste.
   • Do woreczków wolno wkładać tylko kulki, nie inne woreczki.

2. Wypowiedz zaklęcie.

3. Natychmiast po zaklęciu:

   • Wszystkie kulki w woreczkach bez magicznej kulki znikają.
   • Kulki w woreczku z magiczną kulką są chronione i nie znikają. Usunięcie skutków ubocznych zaklęcia kosztuje jednak pieniądze. Jeśli magiczna kulka była w woreczku $i$ zawierającym $j$ kulek, koszt wynosi $A[i] \times j+B[i]$ wonów ($A[i] \ge 0$, $B[i] \ge 1$).

Magiczna kulka nigdy nie znika, więc powtarzając procedurę, aż pozostanie tylko jedna, można ją znaleźć.

Wybierz strategię rozdzielania kulek, aby zminimalizować łączny koszt w najgorszym przypadku. Innymi słowy, znajdź najmniejsze $w$, dla którego można znaleźć magiczną kulkę za co najwyżej $w$ wonów, niezależnie od tego, która z $k+1$ kulek jest magiczna.

Napisz funkcję rozwiązującą to zadanie dla każdego $k$ od $0$ do $N-1$.

Szczegóły implementacji

Zaimplementuj poniższą funkcję.

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

• $N$: maksymalna liczba kulek.
• $A,B$: tablice długości $M$. Dla każdego $i$ ($0 \le i \le M-1$), jeśli magiczna kulka jest w woreczku $i$ zawierającym $j$ kulek, koszt wynosi $A[i] \times j+B[i]$ wonów.
• Zwróć tablicę $C$ długości $N$. Dla każdego $k$ ($0 \le k \le N-1$) wartość $C[k]$ to najmniejszy koszt w najgorszym przypadku, w wonach, znalezienia magicznej kulki wśród $k$ zwykłych i jednej magicznej.

Przesłany kod nie może w żadnym miejscu wykonywać funkcji wejścia/wyjścia.

Przykład

Przykład 1

Rozważ przypadek $N=3$, $M=2$, $A=[1,3]$, $B=[2,1]$.

Program oceniający wywołuje funkcję następująco.

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

Dla $k=0$ jedyna kulka jest magiczna, więc koszt znalezienia wynosi $0$ wonów.

Dla $k=1$ umieść po jednej kulce w każdym woreczku. Jeśli magiczna jest w woreczku $0$, koszt wynosi $A[0] \times 1+B[0]=1 \times 1+2=3$ wonów; jeśli w $1$, wynosi $A[1] \times 2+B[1]=3 \times 1+1=4$ wonów. Koszt w najgorszym przypadku to $4$ wony.

Dla $k=2$ można użyć następującej strategii, oznaczając kulki przez $X,Y,Z$.

• Umieść $X,Z$ w woreczku $0$, a $Y$ w $1$, po czym wypowiedz zaklęcie.

  • Jeśli magiczna kulka jest w woreczku $0$, koszt wynosi $A[0] \times 2+B[0]=1 \times 2+2=4$ wonów i zostają tylko $X,Z$. Umieść teraz $Z$ w woreczku $0$, a $X$ w $1$ i wypowiedz zaklęcie.

    • Jeśli magiczna kulka jest w woreczku $0$, koszt wynosi $A[0] \times 1+B[0]=1 \times 1+2=3$ wonów i zostaje tylko $Z$.

    • Jeśli magiczna kulka jest w woreczku $1$, koszt wynosi $A[1] \times 1+B[1]=3 \times 1+1=4$ wonów i zostaje tylko $X$.

  • Jeśli magiczna kulka jest w woreczku $1$, koszt wynosi $A[1] \times 1+B[1]=3 \times 1+1=4$ wonów i zostaje tylko $Y$.

W tej strategii łączny koszt wynosi $4+4=8$ wonów dla magicznej $X$, $4$ wony dla $Y$ i $4+3=7$ wonów dla $Z$. Zatem najgorszy koszt to $8$ wonów.

Funkcja powinna zwrócić $[0,4,8]$.

Przykład 2

Rozważ przypadek $N=13$, $M=2$, $A=[1,3]$, $B=[2,1]$.

Program oceniający wywołuje funkcję następująco.

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

Funkcja powinna zwrócić $[0,4,8,11,13,17,18,20,24,25,27,29,30]$.

Przykład 3

Rozważ przypadek $N=12$, $M=3$, $A=[5,3,0]$, $B=[1,4,6]$.

Program oceniający wywołuje funkcję następująco.

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

Funkcja powinna zwrócić $[0,6,7,12,13,16,17,18,19,20,22,23]$.

Ograniczenia

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

Podzadania

1. ($3$ punktów) $A[0]=A[1]=\cdots=A[M-1]$, $B[0]=B[1]=\cdots=B[M-1]$.
2. ($4$ punktów) $N \le 5\,000$, $M=2$.
3. ($7$ punktów) $M=2$.
4. ($12$ punktów) $A[i]=0$, $B[i] \le 1\,000$ (dla każdego $0 \le i \le M-1$).
5. ($25$ punktów) $N \le 10\,000$, $M \le 10$.
6. ($17$ punktów) $M \le 100$.
7. ($32$ punktów) Brak dodatkowych ograniczeń.

Przykładowy program oceniający

Format wejścia przykładowego programu oceniającego jest następujący.

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

Format wyjścia przykładowego programu oceniającego jest następujący.

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