题目描述

公元 $2077$ 年，由于全球气候变暖，海平面上涨，现在只有一条直线上的 $n$ 个岛未被海水淹没，第 $i$ 个小岛的初始海拔为 $h_{i}$。初始时，所有岛将连成一个“大岛”。

不幸的是，在接下来的 $q$ 天内，海平面将继续上涨，第 $i$ 天的海平面高度为 $x_{i}$ （以初始海平面高度为准）。

海水将淹没所有海拔小于等于其高度的岛屿。因此，海水的上涨可能会使一个“大岛”分裂成几个“小岛”，海水的下降也可能会使几个“小岛”连成一个“大岛”。这无疑会使得物资的运输变得更加困难，因此，你需要回答每天的海水会将这 $n$ 个岛划分成几个联通的小岛。

在某些情况下，你需要在线回答每一天的情况。

在线:对于每次询问，你必须计算出正确答案之后才能获取下一次询问的正确输入值。

输入格式

第一行三个整数 $n,q,c$。
第二行 $n$ 个整数 $h_{1 \sim n}$。
接下来 $q$ 行，每行一个整数 $x_{i}$。
每个 $x_{i}$ 均要异或上 $lastans \times c$，其中 $lastans$ 表示上一次询问的答案，特别的，当 $i=1$ 时，$lastans = 0$ 。

输出格式

共 $q$ 行，表示每一天的答案。

6 4 0
2 4 2 3 4 1
1
2
3
4

1
2
2
0

样例1解释

海平面高度为 $1$ 时，第 $1,2,3,4,5$ 个岛未被淹没，他们将连成一个“小岛”，答案为 $1$。
海平面高度为 $2$ 时，第 $2,4,5$ 个岛未被淹没。第 $4,5$ 个岛将连成一个“小岛”，第 $2$ 个岛自成一个“小岛”，答案为 $2$。
海平面高度为 $3$ 时，第 $2,5$ 个岛未被淹没，答案为 $2$。
海平面高度为 $4$ 时，所有的岛都被淹没了，答案为 $0$。

10 10 1
14 15 4 7 7 11 14 13 13 4 
1
6
15
3
14
9
15
2
7
5

1
2
2
1
0
2
2
1
2
2

样例2解释

此样例与下面这个样例等价：

10 10 0
14 15 4 7 7 11 14 13 13 4 
1
7
13
1
15
9
13
0
6
7

数据规模与约定

对于全部数据，保证 $1 \le n,q \le 10^{6},0 \le h_{i},x_{i} \le 10^{9},0 \le c \le 10^{3}$。

有合理的子任务依赖。