3963: 「LibreOJ NOI Round #1」北校门外的回忆

回到了正常的时空，神犇和 LCR 暂时过着安宁又平静的生活，他们回想起三年前的往事…… > 秋日的北校门格外美丽，这天，神犇和 LCR 第一次因化学中二而相遇…… 令神犇难以忘怀的是，他与 LCR 相遇是在校门外的树下。那棵树的奇特形态深深印在神犇的脑中。神犇称这棵树是一棵“K 项树”。 为了纪念他和 LCR 的第一次相遇，神犇后来写的树状数组都是以 K 进制而非二进制为基的。 神犇的机房里有一位名叫 LCA 的蒟蒻，一天他碰巧欣赏到了神犇的代码，它发现神犇的树状数组是这么写的： ``` function add(x,v) while x <= n do s[x] = s[x] xor v x = x + lowbitv(x) end while end function function query(x) ans = 0 while x > 0 do ans = ans xor s[x] x = x - lowbit(x) end while return ans end function ``` 其中： * $\mathrm{lowbit}(x)$ 表示 $K$ 进制下 $x$ 的最低非零位的值（例如当 $K=5$ 时，$\mathrm{lowbit}(230_{(5)})=30_{(5)}=15_{(10)}$） * $\mathrm{lowbitv}(x)$ 表示 $K$ 进制下 $x$ 的最低非零位的位值（即该位为 1 其它位都为 0 时的数值，例如当 $K=5$ 时，$\mathrm{lowbitv}(230_{(5)})=10_{(5)}=5_{(10)}$） 这份代码的作用是维护一个长度为 $n$ 的序列 $A$，支持单点**异或**上一个值和求前缀**异或和**。$s[i]$ 维护的是 $\mathop{\oplus}\limits_{i\in (s[i]-\mathrm{lowbit}(s[i]),s[i]]} A_i$。（$\oplus$ 表示按位异或） LCA 觉得这种写法十分不错，于是自己也这么写，但总是写挂的 LCA 漏打了一个字符，还把 $K$ 的值设定得大了很多。 也就是说，LCA 的代码是这么写的： ``` function add(x,v) while x <= n do s[x] = s[x] xor v x = x + lowbit(x) //注意，这里是 lowbit，这也是两份代码唯一的区别 end while end function function query(x) ans = 0 while x > 0 do ans = ans xor s[x] x = x - lowbit(x) end while return ans end function ``` **注意：两个函数调用的都是 $\mathrm{lowbit}$。** 紧接着 LCA 就发现自己的代码跑得比谁都慢，他百思不得其解，只好来请你帮他解决这个问题。 请写一个和 LCA 的程序的输出相同的程序。 **注意，你的任务是写一个和 LCA 的程序输出相同的程序，而不是正确的程序。**

第一行三个正整数 $n,q,K$，表示序列长度，操作数和进制的基数。**序列初始全为 0，LCA 的 s 数组也会初始化为全 0**。 接下来 $q$ 行每行格式是下列之一： * $\texttt{1 x v}$ 给 $A_x$ 的值异或上 $v$。LCA 会调用 $\mathrm{add}(x,v)$。 * $\texttt{2 x}$ 查询 $\mathop{\oplus}\limits_{i\in (0,x]} A_i$。LCA 会输出一行一个整数，为调用 $\mathrm{query}(x)$ 的结果。

对于每个 2 操作，输出一个整数表示 **LCA 程序的输出**。 **注意，你的任务是写一个和 LCA 的程序输出相同的程序，而不是正确的程序。**

7 16 5
1 1 10
2 1
1 4 15
2 4
1 6 10
1 4 15
2 6
2 6
1 6 5
1 5 12
2 3
1 2 5
1 4 5
2 5
1 6 0
1 5 5

10
5
10
10
0
12