Bajtek 喜欢在闲暇时间解决算术谜题。其中大多数谜题都非常相似：对于给定的参数 $a, b, c$ 和一个数字 $n$，我们希望构造一个求值结果为 $n$ 且花费最小的算术表达式。

算术表达式的递归定义如下：1 是一个求值结果为 $1$ 且花费为 $a$ 的算术表达式。接着，如果 $X$ 和 $Y$ 分别是花费为 $x$ 和 $y$、求值结果分别为 $p$ 和 $q$ 的算术表达式，则：

1. $(X + Y)$ 是一个求值结果为 $p + q$ 且花费为 $x + y + b$ 的算术表达式。
2. $(X \times Y)$ 是一个求值结果为 $p \times q$ 且花费为 $x + y + c$ 的算术表达式。

例如，$((1 + 1) \times (1 + 1)) \times (1 + 1)$ 是一个合法的算术表达式，其求值结果为 $8$，花费为 $6a + 3b + 2c$。

Bajtek 想要知道求值结果分别为从 $1$ 到 $n$ 的连续整数的算术表达式的最小花费。他很快意识到手动计算这些花费相当繁琐，于是向他的程序员朋友——你——寻求帮助。请帮他确定这些最小表达式花费！

输入格式

输入的第一行，也是唯一的一行，包含四个整数 $n, a, b, c$（$1 \le n \le 3000$，$1 \le a, b, c \le 10^9$）。

输出格式

输出的第一行，也是唯一的一行，应包含 $n$ 个由单个空格分隔的整数，其中第 $i$ 个数字表示求值结果为 $i$ 的算术表达式的最小花费。

样例

输入样例 1

6 1 4 2

输出样例 1

1 6 11 14 19 19

说明

下表展示了求值结果为连续整数且花费最小的表达式：

样例测试： 样例 0a 即为上述样例。此外：

• 0b: $n = 9, a = 2, b = 3, c = 1$
• 0c: $n = 200, a = 1, b = 2, c = 3$
• 0d: $n = 2500, a = 1, b = 1, c = 1$
• 0e: $n = 3000, a = b = c = 10^9$

子任务

测试用例被分为以下子任务。每个子任务的测试由一个或多个独立的测试用例组组成。