题目描述

小Z想把若干个 1 使用加法、乘法两种规则拼接为一个表达式，其中使用一次加法的花费为 b，使用一次乘法的代价为 c，使用单独一个数字 1 也需要花费 a。

求得可以使表达式结果为 i 的最小花费。

例如，$\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$）。分别表示初始 1 的最大个数、三种操作的相应花费。

输出格式

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

输入输出样例

6 1 4 2

1 6 11 14 19 19

样例 $\tt \#1$说明

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

数据范围

本题采用捆绑测试。