Hide

Problem F
Virkne

Languages da de en et fi lt lv pl uk

Virkne no naturāliem skaitļiem $(x_1, \ldots , x_ m)$ ir laba, ja $x_1 = 1$ un katram $1 < j \leq 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 \leq 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, \ldots , w_ n$ definēsim svaru no kādas veselas skaitļu virknes $(x_1, \ldots , x_ m)$, kas apmierina $1 \leq x_ j \leq n$ visiem $1 \leq j \leq m$, kā

\[ w_{x_1} + \cdots + w_{x_ m}. \]

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\leq v\leq 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,\ldots ,s_ n$.

Ievaddati

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

Izvaddati

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

Ierobežojumi un vērtēšana

Vienmēr izpildās ierobežojumi $1\leq n \leq 30\, 000$ un $1\leq w_ i \leq 10^6$ visiem $1\leq i \leq 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.

Grupa

Punkti

Ierobežojumi

$1$

$11$

$n\leq 10$

$2$

$10$

$n\leq 300$, $w_1=\cdots =w_ n = 1$

$3$

$10$

$n\leq 300$, $w_1=\cdots =w_ n$

$4$

$9$

$n\leq 1400$, $w_1=\cdots =w_ n = 1$

$5$

$45$

$n\leq 5000$

$6$

$15$

Bez papildu ierobežojumiem

Sample Input 1 Sample Output 1
3
10
42
1
10
52
53