【问题描述】

考虑将Fenwick Tree 扩展到 $k$ 进制意义下，C++代码如下：

void add(int x, int y) {
    while (x <= n) {
        s[x] ^= y;
        x += lowbit(x);
    }
}
int sum(int x) {
    int res = 0;
    while (x > 0) {
        res ^= s[x];
        x -= lowbit(x);
    }
    return res;
}

其中，$\texttt{lowbit(x)}$ 的定义为 $x$ 在 $k$ 进制下最低非 0 位的值。比如 $k=5,\texttt{lowbit}(120)=20$。

但是上述代码并不能正确地维护前缀异或和，甚至会出现TLE。不过并不会出现死循环，现请你快速维护上面的两个函数。

【输入格式】

从文件d.in中读入数据。

输入数据第一行包含三个正整数 $n,q,k$ ，分别表示序列长度，操作次数和进制。

接下来 $q$ 行每行描述一个操作，具体如下：

$1\space x\space y$ ，表示执行 $\texttt{add}(x,y)$ 。

$2\space x\space y$ ，表示输出 $\texttt{sum}(x)$ 。

【输出格式】

输出到文件d.out中。

对于每个 2 操作，输出一行表示询问的结果。

【样例输入输出】

样例2,3 请见下发文件。

【数据范围】

对于所有数据，有 ：

$1 \leq x \leq n \leq 10^9, 1 \leq q,k \leq 2 \times 10^5,0 \leq y \leq 10^9$