Life

You are given two arrays $A$ and $B$ of $N$ integers each, and two integers $U$ and $D$. The $i$-th elements of $A$ and $B$ are $A_i$ and $B_i$.

Define $f(n)$ as follows.

• For $i = 1, 2, \cdots, n$, in order, do the following.
  1. Choose one of $A_i$ and $B_i$.
  2. For every $j$ with $i < j \le n$, if you chose $A_i$, the values of $A_j$ and $B_j$ each increase by $U$. If you chose $B_i$, the values of $A_j$ and $B_j$ each decrease by $D$.

$f(n)$ is the minimum sum of the chosen numbers over the $2^n$ ways to choose.

For every integer $n$ with $1 \le n \le N$, find $f(n)$.

The first line contains $N$, $U$, and $D$, separated by spaces. ($1 \le N \le 300\,000$, $1 \le U, D \le 10^6$)

The second line contains $A_1, A_2, \cdots, A_N$, separated by spaces. ($0 \le A_i \le 10^6$)

The third line contains $B_1, B_2, \cdots, B_N$, separated by spaces. ($0 \le B_i \le 10^6$)

Print $N$ lines. On the $n$-th line, print $f(n)$.