为了制作纸雪花，你需要在一张纸的多个位置进行折叠，然后从折叠后的纸上剪掉一些部分。当你展开纸张时，如果折叠和剪裁选择得当，它会形成非常漂亮的图案。

Samantha 最近迷上了这种爱好，但她加入了一些“现代艺术”的元素。首先，她研究如何折叠一条长度为 $L$ 皮米的纸带（Samantha 喜欢非常精确地测量她的折叠和剪裁）。她将纸带放在实数轴上，一端固定在 $0$ 点，另一端在 $L$ 点。左端 $0$ 点是固定端，另一端 $L$ 是活动端。

接着，她进行了一系列折叠。第一次折叠时，Samantha 在距离活动端 $f_1$ 皮米处折痕，并将活动端向左折叠。此时活动端指向左侧。第二次折叠时，她在距离活动端 $f_2$ 皮米处（$f_2 < f_1$）对纸张的顶部进行折痕，并将纸张顶部向右折叠过该折痕点。此时活动端指向右侧。

她以这种方式交替进行前后折叠。在每一步中，她都在距离活动端 $f_i$ 皮米处（$f_i < f_{i-1}$）对纸张顶部进行折痕，并将活动端折过折痕点。

现在，她将在 $M$ 个不同的位置剪开纸张，这将把纸张分成 $M+1$ 堆。每一堆可能包含零层或多层纸。下图展示了第一个样例输入中折叠后的纸张、剪裁位置（实线）以及纸张折叠的 $x$ 坐标（虚线）。

每一堆纸的总长度是多少？

输入格式

第一行包含三个整数 $N$ ($1 \le N \le 10^5$)，表示折叠次数；$M$ ($1 \le M \le 10^5$)，表示剪裁次数；以及 $L$ ($2 \le L \le 10^{18}$)，表示纸张的长度（单位为皮米）。

第二行描述折叠情况。该行包含 $N$ 个整数 $f_1, f_2, \dots, f_N$，表示第 $i$ 次折叠发生在距离活动端 $f_i$ 皮米处。这些值满足 $1 \le f_N < f_{N-1} < \dots < f_1 < L$。

第三行描述剪裁情况。该行包含 $M$ 个整数 $c_1, c_2, \dots, c_M$，表示第 $i$ 次剪裁发生在距离固定端 $c_i$ 皮米处。这些值满足 $-10^{18} \le c_1 < c_2 < \dots < c_M \le 10^{18}$。

输出格式

按从左到右的顺序，输出每一堆纸的总长度。

样例

样例输入 1

4 2 20
19 17 11 7
1 6

样例输出 1

5 13 2

样例输入 2

1 1 10
9
0

样例输出 2

8 2

样例输入 3

1 2 1000000000000000000
500000000000000000
0 500000000000000000

样例输出 3

0 1000000000000000000 0