Problem F
Virkne

Virkne no naturāliem skaitļiem $(x_1,\dots ,x_m)$ ir laba, ja $x_1=1$ un katram $1<j\le m$ izpildās vai nu $x_j=x_{j-1}+1$ vai $x_j=x_k\cdot x_l$ kādām $k$ un $l$ vērtībām ar $0<k\le l<j$. Piemēram, virknes $(1,1)$ un $(1,2)$ abas ir labas, bet virkne $(1,3)$ nav laba. Dotiem $n$ veseliem skaitļiem $w_1,\dots ,w_n$ definēsim svaru no kādas veselas skaitļu virknes $(x_1,\dots ,x_m)$, kas apmierina $1\le x_j\le n$ visiem $1\le j\le m$, kā

Piemēram, dotiem svariem $w_1=10$, $w_2=42$, $w_3=1$, virknes $(1,1)$ svars ir $20$ un virknes $(1,3)$ svars ir $11$. Katram $1\le v\le n$ definēsim $s_v$ kā mazāko iespējamo svaru kādai labai skaitļu virknei, kas satur skaitli $v$.

Jūsu uzdevums ir noteikt vērtības $s_1,\dots ,s_n$.

Ievaddati

Pirmā ievada rinda satur veselo skaitli $n$, svaru skaitu. Nākamās $n$ rindas satur svarus, veselus skaitļus $w_1,\dots ,w_n$.

Izvaddati

Izvadiet $n$ rindas, kas satur $s_1$, $\dots$, $s_n$ šādā secībā.

Ierobežojumi un vērtēšana

Vienmēr izpildās ierobežojumi $1\le n\le 30000$ un $1\le w_i\le {10}^6$ visiem $1\le i\le n$.

Jūsu risinājums tiks pārbaudīts uz vairākām testu grupām. Katra grupa ir vērta noteiktu punktu skaitu. Katra testu grupa satur vairākus testus. Lai saņemtu punktus par testu grupu, ir jāatrisina visi testi testu grupā. Jūsu gala rezultāts būs lielākais punktu skaits, kas iegūts ar vienu risinājuma iesniegumu.

3
10
42
1

10
52
53