非常有意思的一道题（虽然确实容易想不出来）。
题意
维护一个 $0 \sim 2^n-1$ 的序列，支持两个操作：将下标为偶数的数按序提前，将下标为奇数的数按序后置；将下标为偶数的数按序后置，将下标为奇数的数按序提前。
解析
我们考虑两种操作的实质。
第一种操作（偶前奇后）：对于下标为 $x$ 的数，若 $x$ 为偶数，则它的新下标为 $\frac{x}2$；若 $x$ 为奇数，则它的新下标为 $\frac{x}{2}+\frac{n}{2}$。
第二种操作（奇前偶后）：对于下标为 $x$ 的数，若 $x$ 为偶数，则它的新下标为 $\frac{x}{2}+\frac{n}{2}$；若 $x$ 为奇数，则它的新下标为 $\frac{x}{2}$。
见到这么多的除以二，我们考虑到二进制。我们假定一个操作前某数的下标为 $x=(a_na_{n-1}a_{n-2} \dots a_2a_1 )$，同时我们又发现偶数的末位为 $0$，奇数的末位为 $1$，那么我们进行一次一操作，就是将下标变为 $(a_1a_na_{n-1} \dots a_3a_2 )$，也就是将最后一位移到第一位，再将其他位都向后推一位。同样能够发现，我们进行一次二操作，就是将下标变为 $((a_1\operatorname{xor}1)a_na_{n-1} \dots a_3a_2 )$，也就是将末位异或 $1$ 之后再进行之前的操作。因此假设我们进行 $t$ 次操作后（$t < n$），就是把最后的 $t$ 位以相同的顺序移到了前面（即，若原先三位在最后是 $(a_3a_2a_1)$ ，则它被移到了前面之后这三位依然是 $(a_3a_2a_1)$，内部顺序不变），把其他位移到了最后（当然其中可能有一些需要异或）。
现在，我们得到的是一个操作后的数的下标，输出对应的数其实就是输出原始的下标。因此，我们可以用 $cnt$ 记录一下进行了几次一操作（容易发现，当 $n=cnt$ 时，所有位都移了一轮，此时可以将 $cnt$ 归零），然后将这个数的末 $n-cnt$ 位向前移 $cnt$ 位，将最前的 $cnt$ 位向后移动 $n-cnt$ 位，这样，我们就得到了原先的数，但是注意，我们此时尚未处理异或操作。
容易发现，每次异或实际是对第 $cnt+1$ 位进行异或，那么我们可以用一个变量 $v$ 记录原始每一位上是否需要异或，详见代码注释。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60;
int n,m,t[N],v,x,opt,cnt;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) t[i]=(t[i-1]<<1)+1;//可以提前处理一下全 1 数
for(int i=1;i<=m;i++){
scanf("%lld%lld",&opt,&x);
if(opt==1){
v^=x<<cnt;//将第 cnt+1 位打上标记，若 x=0 显然这个操作是无意义的
cnt++;
if(cnt==n) cnt=0;//如果 cnt=n 了，一轮结束，cnt 归零
}
else{
printf("%lld\n",(((x&t[n-cnt])<<cnt)|(x>>(n-cnt)))^v);
//(x&t[n-cnt])<<cnt 是将最后 n-cnt 位向前移动
//x>>(n-cnt) 是将前 cnt 位向后移动，再用 | 合并
//由于我们前面的标记打在原始序列上，所以要先将该数列还原后再 ^v
}
}
return 0;
}