Problem Statement

There are $N$ sandglasses, each consisting of a part $A$ and a part $B$. Each part can hold at most $K$ grams of sand.

The $i \ (1 \leq i \leq N)$-th sandglass has part $a_i$ on top, with $b_i$ grams of sand in part $A$ and $K-b_i$ grams of sand in part $B$. Sand falls into the lower part at a rate of $1$ gram per $1$ second. Here, the given $b$ satisfies $b_i \neq b_j$ if $i \neq j$.

While the sand in the sandglasses is falling, you repeat the following operations.

• If the lower part of a sandglass contains $K$ grams of sand, turn it over.
• If there is a pair of sandglasses with the same amount of sand in part $A$, turn both of them over.

Here, turning over a sandglass is considered to take no time, and the sand starts falling at the moment the sandglass is turned over.

Also, due to the constraints, it never happens that $3$ or more sandglasses have the same amount in part $A$.

Find the amount of sand in part $A$ of each sandglass after $T$ seconds.

Input

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

• All input values are integers.
• $1 \leq N \leq 2 \times 10^5$
• $2 \leq K \leq 10^{9}$
• $1 \leq T \leq 10^{9}$
• $a_i$ is A or B $(1 \leq i \leq N)$
• $0 < b_i < K \ (1 \leq i \leq N)$
• $b_i \neq b_j$ when $i \neq j$

Output

Output $N$ values. The $i$-th value should be the amount of sand in part $A$ of sandglass $i$ after $T$ seconds. (Corrected at 21:48)

Sample

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