인생

$N$개의 정수로 이루어진 두 배열 $A$, $B$와 두 정수 $U$, $D$가 주어진다. 배열 $A$, $B$의 $i$번째 원소는 각각 $A\_i$, $B\_i$이다.

$f(n)$을 다음과 같이 정의한다.

• 아래 과정을 $i = 1, 2, \cdots, n$에 대해 순서대로 수행한다.

  1. $A\_i$와 $B\_i$ 중 하나를 고른다.
  2. 이후 $i < j \le n$을 만족하는 모든 $j$에 대해, $A\_i$를 골랐다면 $A\_j$와 $B\_j$의 값이 $U$만큼 증가하고, $B\_i$를 골랐다면 $A\_j$와 $B\_j$의 값이 $D$만큼 감소한다.

• $f(n)$은 수를 고르는 $2^n$가지 방법 중, 고른 수들의 합의 최솟값이다.

$1$ 이상 $N$ 이하의 모든 정수 $n$에 대해, $f(n)$의 값을 구해보자.

첫째 줄에 배열의 길이 $N$과 양의 정수 $U$, $D$가 공백으로 구분되어 주어진다. $(1 \le N \le 300\ 000$; $1 \le U, D \le 10^6)$

둘째 줄에 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다. $(0 \le A\_i \le 10^6)$

셋째 줄에 $B\_1, B\_2, \cdots, B\_N$이 공백으로 구분되어 주어진다. $(0 \le B\_i \le 10^6)$

$N$개의 줄에 걸쳐 답을 출력한다. $n$번째 줄에는 $f(n)$을 출력한다.