Sequence

A sequence of positive integers $(x_1,\ldots,x_m)$ is good if $x_1 = 1$ and for each $1 < j \leq m$ we have either $x_j = x_{j-1}+1$ or $x_j = x_k \cdot x_l$ for some $k$ and $l$ with $0 < k \leq l < j$. For instance, the sequences $(1,1)$ and $(1,2)$ are both good, but the sequence $(1,3)$ is not good.

Given $n$ integers $w_1,\ldots,w_n$, the weight of an integer sequence $(x_1,\ldots,x_m)$ with $1 \leq x_j \leq n$ for each $1 \leq j \leq m$ is

$w_{x_1} + \cdots + w_{x_m}.$

For instance, given the weights $w_1=10$, $w_2=42$, $w_3=1$, the weight of $(1,1)$ is $20$ and the weight of $(1,3)$ is $11$.

For $1 \leq v \leq n$, let $s_v$ be the smallest possible weight of a good sequence that contains the value $v$.

The first line contains the integer $n$, the number of weights. Each of the next $n$ lines contains one integer weight $w_1, \ldots, w_n$.

Print $n$ lines. The $v$-th line contains $s_v$, for $v = 1, \ldots, n$.

$1 \leq n \leq 30\,000$ and $1 \leq w_i \leq 10^6$ for each $1 \leq i \leq n$.