在这里感谢这篇题解的作者，代码解释得很清晰~
经过打表观察，可以发现：当\(1\le x \le k\)时
于是可以对每条链开一棵动态开点线段树，再开一棵线段树处理不在单点上的点，一起用来模拟题目所给的树状数组（\(N\le10^{9}\)，直接开树状树组会炸）。
于是可以这么做修改操作：
对于不在链上的点，最多只会跳\(log_{2}^{k}*log_{k}^{n}=log_{2}^{n}\)次就会跳到\(n\)之外或跳到链上，暴力更新就完事了。
对于在链上的点，我们可以找到这条链的链头(找链头的方法详见代码)，求出这个点到链头的距离\(dis\)，区间更新\(dis\)和链尾之间的点。
查询也差不多的。
更详细的解释见代码：
#include <bits/stdc++.h>
#define N 200010
using namespace std;
int k;
inline void rd(int &x){
int y=0,f=1;char c=getchar();
while(c<'0' || c>'9' ){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9')y=y*10+(c^48),c=getchar();
x=y*f;
}
int num[N],jw[N],go[N][20],to[N][20],pr[N],a[N],fr,dis,u;
bool vis[N];
inline int lowbit(int x){
while(x%k==0) x/=k;
return x%k;
}
inline int lowbitv(int x){
register int lg=0;
while (x%k==0) x/=k,lg++;
x%=k;
while (lg) x*=k,lg--;
return x;
}
void init()//预处理
{
//jw[i]:i所在链上的进位次数
register int cnt,i,j,w,l;
for(i=1;i<=k;++i) for(j=i;j%2==0;j/=2,++pr[i]);
for(i=1;i<k;++i){
cnt=w=0;
if(vis[i] || pr[i]<pr[k]) continue;
int x=i*2%k;a[++cnt]=i,vis[i]=1;
while(x!=i) a[++cnt]=x,vis[x]=1,x=x*2%k;
for(j=1;j<=cnt;++j) w+=(a[j]*2>=k);
for(j=1;j<=cnt;++j){
jw[a[j]]=w,num[a[j]]=cnt;
(j==1)?x=cnt:x=j-1;
to[a[j]][0]=a[x];
go[a[j]][0]=(a[x]*2>=k);
}
//to[i][j]:i向前跳j步跳到的点
//go[i][j]:i向前跳j步的进位次数
for(j=1;j<=18;++j)
for(l=1;l<=cnt;++l){
to[a[l]][j]=to[to[a[l]][j-1] ][j-1];
go[a[l]][j]=go[a[l]][j-1]+go[to[a[l]][j-1] ][j-1];
}
}
}
void GetF(int x)//求链头
{
int lg=0;
while(x%k==0) x/=k,lg++;
fr=lowbit(x),dis=1;int u=(x-fr)/k,i;//u:x的进位次数
//dis=跳的环数*环的长度+剩余长度（没跳完整个环）
dis+=u/jw[fr]*num[fr];
u%=jw[fr];
for(i=18;i>=0;--i){
if(go[fr][i]<=u){
u-=go[fr][i];
dis+=(1<<i);
fr=to[fr][i];
}
}
while(lg) fr*=k,lg--;//由lowbit(x)的链头还原回去x的链头
}
#define mid ((l+r)>>1)
int root1,root2,root3;
struct tr{ int ls,rs,x; };
struct qwq{
tr t[N*60];
int sz=0;
void update(int &o,int l,int r,int L,int R,int v){
if(!o) o=++sz;
if(L<=l && r<=R){
t[o].x^=v;
return;
}
if(L<=mid) update(t[o].ls,l,mid,L,R,v);
if(R>mid) update(t[o].rs,mid+1,r,L,R,v);
}
int query(int o,int l,int r,int x){
if(l==r || !o) return t[o].x;
if(x<=mid) return t[o].x^query(t[o].ls,l,mid,x);//不用pushup的原因（异或只用异或一遍）
else return t[o].x^query(t[o].rs,mid+1,r,x);
}
} Point,Chain,Front;
//Point:不在链上的点
//Chain:链上的点的更新（以链头的点值为根）
//Front:链头在Chain上的位置
int main()
{
int n,q,op,x,v,ans;
rd(n),rd(q),rd(k);
init();
while(q--){
rd(op),rd(x);
if(op==1){
rd(v);
while(x<=n && pr[lowbit(x)]<pr[k]){
Point.update(root2,1,n,x,x,v);
x+=lowbitv(x);
} //暴力跳
if(x>n) continue;
GetF(x);
root1=Front.query(root3,1,n,fr);
int tmp=root1;Chain.update(root1,1,n,dis,n,v);
//Chain相当于重构了编号,比如说链头为x,则线段树里编号为2的元素实际上是原树状数组编号为x+lowbit(x)的元素
if(!tmp) Front.update(root3,1,n,fr,fr,root1);
} else{
ans=0;
while(x){
if(pr[lowbit(x)]<pr[k]) ans^=Point.query(root2,1,n,x);
else{
GetF(x);
root1=Front.query(root3,1,n,fr);
if(root1) ans^=Chain.query(root1,1,n,dis);
}
x-=lowbitv(x);
}
printf("%d\n",ans);
}
}
}