题目背景

滥用评测者将被封号。

题目描述

给定正整数 $n,a,b,c$。对于 $i=1,2,\ldots,n$，构造一个代价最小的表达式，使得表达式求值的结果为 $i$。只需要求出最小的代价。

---

我们给出表达式及其代价的定义。

• $\texttt{1}$ 是代价为 $a$、求值结果为 $1$ 的表达式。
• 若 $X,Y$ 的代价分别为 $x,y$，且求值结果分别为 $p,q$：
  • $(X+Y)$ 是代价为 $x+y+b$、求值结果为 $p+q$ 的表达式。
  • $(X\times Y)$ 是代价为 $x+y+c$、求值结果为 $p\cdot q$ 的表达式。

例如，$\tt(( 1 + 1) × (1 + 1)) × (1 + 1)$ 是代价为 $6a+3b+2c$，求值结果为 $8$ 的表达式。

输入格式

一行四个正整数 $n,a,b,c$（$1\le n\le 3\, 000$，$1\le a,b,c\le10^9$）。

输出格式

$n$ 个正整数，第 $i$ 个正整数表示求值结果为 $i$ 的表达式的最小代价。

6 1 4 2

1 6 11 14 19 19

提示

样例解释

下表展示了可以得到 $1\sim 6$ 的最小代价的表达式。

求值结果	表达式	代价
$1$	$\tt 1$	$a = 1$
$2$	$\tt (1+1)$	$2a + b = 2 + 4 = 6$
$3$	$\tt ((1+1)+1)$	$3a + 2b = 3 + 8 = 11$
$4$	$\tt ((1+1)*(1+1))$	$4a + 2b + c = 4 + 8 + 2 = 14$
$5$	$\tt (((1+1)*(1+1))+1)$	$5a + 3b + c = 5 + 12 + 2 = 19$
$6$

大样例

可以在附件中获得大样例。

样例 $\texttt{0a}$ 是题面中展示的样例。此外：

• $\texttt{0b}$： $n = 9, a = 2, b = 3, c = 1$。
• $\texttt{0c}$： $n = 200, a = 1, b = 2, c = 3$。
• $\texttt{0d}$： $n = 2500, a = 1, b = 1, c = 1$。
• $\texttt{0e}$： $n = 3000, a = b = c = 10^9$。

子任务

本题采用捆绑测试。 | 子任务编号 | 限制 | 得分 | | :---------: | :--------------------- | :-----: | | $1$ | $n \le 10$ | $13$ | | $2$ | $n \le 200$ | $31$ | | $3$ | $a = b = c = 1$ | $13$ | | $4$ | 无额外限制 | $43$ |