수열

양의 정수로 이루어진 수열 $(x_1,\ldots,x_m)$이 좋은 수열이라는 것은 $x_1 = 1$이고, 각 $1 < j \leq m$에 대해 $x_j = x_{j-1}+1$이거나, $0 < k \leq l < j$인 어떤 $k$, $l$에 대해 $x_j = x_k \cdot x_l$이 성립하는 것이다. 예를 들어 $(1,1)$과 $(1,2)$는 모두 좋은 수열이지만, $(1,3)$은 좋은 수열이 아니다.

정수 $n$개 $w_1,\ldots,w_n$이 주어졌을 때, 각 $1 \leq j \leq m$에 대해 $1 \leq x_j \leq n$을 만족하는 정수 수열 $(x_1,\ldots,x_m)$의 가중치는 다음과 같다.

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

예를 들어 가중치가 $w_1=10$, $w_2=42$, $w_3=1$로 주어지면, $(1,1)$의 가중치는 $20$이고 $(1,3)$의 가중치는 $11$이다.

$1 \leq v \leq n$에 대해, $s_v$는 값 $v$를 포함하는 좋은 수열의 가중치 중 최솟값이다.

첫 줄에 가중치의 개수인 정수 $n$이 주어진다. 이어지는 $n$개의 줄에는 정수 가중치 $w_1, \ldots, w_n$이 한 줄에 하나씩 주어진다.

$n$개의 줄을 출력한다. $v$번째 줄에는 $s_v$를 출력한다($v = 1, \ldots, n$).

$1 \leq n \leq 30\,000$이고, 각 $1 \leq i \leq n$에 대해 $1 \leq w_i \leq 10^6$이다.