时空限制

1S/512M

题目描述

在数轴上有 $n$ 个移动速度为每秒 $1$ 单位的小球，初始时第 $i$ 个小球的位置为 $a_i$，移动方向为 $d_i$。方向只有 $-1$ 和 $1$ 两种，其中 $-1$ 代表向左移动（位置减一），$1$ 代表向右移动（位置加一）。当两个小球位置相同时，小球会发生碰撞，碰撞的一瞬间这两个小球就会交换移动方向。

数轴上还有 $m$ 个墙，第 $i$ 个墙的位置为 $b_i$。小球撞上墙（即小球位置为 $b_i$）的一瞬间移动方向变为相反。

求 $t$ 秒后每个小球的位置。

格式

输入格式

第一行包含三个整数 $n,m,t$，分别表示小球的数量、墙的数量和移动的时间。

第二行包含 $n$ 个整数 $a_i$，分别表示每个小球初始位置。数据保证 $a_i$ 互不相等。

第三行包含 $n$ 个整数 $d_i$，分别表示每个小球初始移动方向。

第四行包含 $m$ 个整数 $b_i$，分别表示每个墙的位置。数据保证 $b_i$ 互不相等，保证对于任意 $1\leq i \leq n$ 且 $1\leq j\leq m$，有 $a_i\neq b_j$。

输出格式

输出一行包含 $n$ 个整数，第 $i$ 个整数表示 $t$ 秒后第 $i$ 个小球的位置。

样例

样例输入 #1

4 1 5
2 1 5 3
-1 -1 -1 1
0

样例输出 #1

3 0 8 4

样例解释 #1

小球的移动状态如下图：

样例输入 #2

6 3 1000
16 205 87 39 1 44
1 1 -1 1 1 -1
210 32 146

样例输出 #2

-937 181 127 65 -952 108

样例输入 #3

2 1 100
100 300
1 -1
200

样例输出 #3

200 200

数据规模

对于 $10\%$ 的数据，$n\leq 1000$，$m=0$，$t\leq 1000$。

对于 $30\%$ 的数据，$m=0$。

对于 $50\%$ 的数据，$m\leq 1$。

对于 $100\%$ 的数据，$1\leq n \leq 10^5$，$0\leq m \leq 10^5$，$1 \leq t \leq 10^{18}$，$0 \leq a_i,b_i \leq 10^{18}$，$d_i\in\{-1，1\}$。数据保证 $a_i$ 互不相等，保证 $b_i$ 互不相等，保证对于任意 $1\leq i \leq n$ 且 $1\leq j\leq m$，有 $a_i\neq b_j$。