転置のクエリだけが時間がかかるので，そこを何とかする． 転置は2回繰り返すともとに戻るので，回数だけ記録しておく． また，行と列は独立に操作可能．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, q;
cin >> n;
cin >> q;
auto f = [&](ll h, ll w) -> ll {
return n*h + w;
};
bool tr = false;
vvll pe(2, vll(n));
rep(i,2) rep(j,n){
pe[i][j] = j;
}
rep(qi,q){
ll op, h,w;
cin >> op;
if(op == 1){
cin >> h >> w;
--h, --w;
swap(pe[0^tr][h], pe[0^tr][w]);
} else if(op == 2){
cin >> h >> w;
--h, --w;
swap(pe[1^tr][h], pe[1^tr][w]);
} else if(op == 3){
tr ^= 1;
} else{
cin >> h >> w;
--h, --w;
if(tr) swap(h,w);
h = pe[0][h];
w = pe[1][w];
cout << f(h,w) << endl;
}
}
return 0;
}
