인생

$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)$을 출력한다.