Problem Statement

Consider a non-empty multiset $S$ in which every element is a power of $2$.

A power of $2$ is an integer that can be expressed as $2^i$ using a non-negative integer $i$.

Here, let $x$ be the number of elements contained in $S$, $y$ be the number of distinct values of the elements, and $2^z$ be the maximum value of the elements, and define the cost of $S$ as $Ax+By+Cz$.

For example, if $S= \{ 1, 1, 2, 8 \}$, then $x=4, y=3, z=3$.

For each non-negative integer $k$ $(0 \leq k \leq N-1)$ less than $N$, answer the following question.

• Consider an $S$ such that the sum of the elements of $S$ leaves a remainder of $k$ when divided by $N$. Find the minimum cost of $S$.

Input

$N$ $A$ $B$ $C$

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A,B,C \leq 10^9$
• All inputs are integers.

Output

Output $N$ lines.
On the $i$-th line, output the answer for $k=i-1$ as an integer.

Sample

3 5 2 1

15
7
8

13 25 35 5

150
60
65
80
70
105
85
115
75
100
110
95
90