問題文

パーツ $A$ とパーツ $B$ からなる砂時計が $N$ 個あり、それぞれのパーツには最大で $K$ グラムの砂が入ります。

$i \ (1 \leq i \leq N)$ 個目の砂時計は、パーツ $a_i$ を上にしており、パーツ $A$ に $b_i$ グラム、パーツ $B$ に $K-b_i$ グラムの砂が入っていて、砂は $1$ 秒あたり $1$ グラム下にあるパーツへ落ちます。ここで、与えられる $b$ において $i \neq j$ ならば $b_i \neq b_j$ が成り立ちます。

あなたは砂時計の砂が落ちている間、以下の操作を繰り返します。

• もし下にあるパーツに $K$ グラムの砂が入っている場合、それをひっくり返す。
• もしパーツ $A$ に入っている砂の量が同じ砂時計の組があるとき、それをどちらもひっくり返す。

ここで、砂時計をひっくり返す時間は考えないものとし、砂時計をひっくり返した瞬間に砂時計の砂が落ち始めるものとします。

また、制約より $3$ つ以上の砂時計において、パーツ $A$ に入る砂時計の量が同じになることはありません。

このとき、$T$ 秒後にそれぞれの砂時計のパーツ $A$ に砂が入っている量を求めてください。

入力

$N$ $K$ $T$
$a_1$ $a_2$ $\dots$ $a_N$
$b_1$ $b_2$ $\dots$ $b_N$

• 入力は全て整数
• $1 \leq N \leq 2 \times 10^5$
• $2 \leq K \leq 10^{9}$
• $1 \leq T \leq 10^{9}$
• $a_i$ は A または B $(1 \leq i \leq N)$
• $0 < b_i < K \ (1 \leq i \leq N)$
• $i \neq j$ のとき $b_i \neq b_j$

出力

$N$ 個出力せよ。 $i$ 個目には $T$ 秒後の砂時計 $i$ のパーツ $A$ に砂が入っている量を出力せよ。(21:48 修正)

サンプル

2 10 15
B A
6 8

1 7

2 3 3
A B
1 2

1 2

9 1992 2023
A B B A B B A B A
19 289 514 318 537 1722 443 972 114

239 1424 1672 1447 1705 1980 1580 1909 989