#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std ;
#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)
#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
const int mod = 1e9 + 7;
int ADD(int a, int b, int m = mod) {
int s = a;
s += b;
if( s >= m )
s -= m;
return s;
}
int MUL(int a, int b, int m = mod) {
return (1LL * a * b % m);
}
int power(int a, int b, int m = mod) {
int res = 1;
while( b ) {
if( b & 1 ) {
res = 1LL * res * a % m;
}
a = 1LL * a * a % m;
b /= 2;
}
return res;
}
ll nC2(ll x) {
return ( x * ( x - 1 ) / 2 );
}
const int maxn = 1e5 + 5;
int n, q;
vi adj[ maxn ];
ll color[ maxn ];
int get( ll x ) {
int c = 0;
while( x ) {
c ++;
x -= (x & -x);
}
return c;
}
void dfs( int u, int p, int k, int lev ) {
if( lev > k ) return;
color[ u ] = (1LL << lev);
for( auto it: adj[u] ) {
if( it != p ) {
dfs(it, u, k, lev + 1);
}
}
}
ll range(int l, int r) {
ll ans = 0;
while( l <= r ) {
ans |= color[ l ];
l ++;
}
return ans;
}
int main() {
cin >> n >> q;
int i;
fr(i, 1, n) {
int x, y;
x = i; y = 2 * x;
if( y <= n ) adj[x].pb( y ), adj[y].pb( x );
x = i; y = 2 * x + 1;
if( y <= n ) adj[x].pb( y ), adj[y].pb( x );
}
while( q-- ) {
int t, x, y, k; sc1( t );
if( t == 1 ) {
sc2( x, k );
dfs( x, 0, k, 0);
} else if( t == 2 ) {
sc2(x, y);
ll ans = 0;
while( x != y ) {
if( x < y ) {
ans |= color[ y ];
y /= 2;
} else {
ans |= color[ x ];
x /= 2;
}
}
ans |= color[ x ];
ans -= ans % 2;
pr1( get( ans ) );
} else {
sc1( x );
int l, r; ll ans = 0;
l = r = x;
while( l <= r ) {
ans |= range(l, r);
l *= 2; r = r * 2 + 1;
r = min(n, r);
}
ans -= ans % 2;
pr1( get( ans ) );
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Ci8vICNpbmNsdWRlICJ0ZXN0bGliLmgiICAKdXNpbmcgbmFtZXNwYWNlIHN0ZCA7CgojZGVmaW5lIGZ0IGZpcnN0CiNkZWZpbmUgc2Qgc2Vjb25kCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSx4LmVuZCgpCgojZGVmaW5lIGxsIGxvbmcgbG9uZyBpbnQKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZpaSB2ZWN0b3I8cGFpcjxpbnQsaW50PiA+CiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KI2RlZmluZSBwbGlpIHBhaXI8cGFpcjxsbCwgaW50PiwgaW50PgojZGVmaW5lIHBpaWkgcGFpcjxwaWksIGludD4KI2RlZmluZSB2aWlpIHZlY3RvcjxwYWlyPHBpaSwgaW50PiA+CiNkZWZpbmUgdmwgdmVjdG9yPGxsPgojZGVmaW5lIHZsbCB2ZWN0b3I8cGFpcjxsbCxsbD4gPgojZGVmaW5lIHBsbCBwYWlyPGxsLGxsPgojZGVmaW5lIHBsaSBwYWlyPGxsLGludD4KI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBtcyh4LCB2KSBtZW1zZXQoeCwgdiwgc2l6ZW9mIHgpCgojZGVmaW5lIHNjMSh4KSBzY2FuZigiJWQiLCZ4KQojZGVmaW5lIHNjMih4LHkpIHNjYW5mKCIlZCVkIiwmeCwmeSkKI2RlZmluZSBzYzMoeCx5LHopIHNjYW5mKCIlZCVkJWQiLCZ4LCZ5LCZ6KQoKI2RlZmluZSBzY2xsMSh4KSBzY2FuZigiJWxsZCIsJngpCiNkZWZpbmUgc2NsbDIoeCx5KSBzY2FuZigiJWxsZCVsbGQiLCZ4LCZ5KQojZGVmaW5lIHNjbGwzKHgseSx6KSBzY2FuZigiJWxsZCVsbGQlbGxkIiwmeCwmeSwmeikKCiNkZWZpbmUgcHIxKHgpIHByaW50ZigiJWRcbiIseCkKI2RlZmluZSBwcjIoeCx5KSBwcmludGYoIiVkICVkXG4iLHgseSkKI2RlZmluZSBwcjMoeCx5LHopIHByaW50ZigiJWQgJWQgJWRcbiIseCx5LHopCgojZGVmaW5lIHBybGwxKHgpIHByaW50ZigiJWxsZFxuIix4KQojZGVmaW5lIHBybGwyKHgseSkgcHJpbnRmKCIlbGxkICVsbGRcbiIseCx5KQojZGVmaW5lIHBybGwzKHgseSx6KSBwcmludGYoIiVsbGQgJWxsZCAlbGxkXG4iLHgseSx6KQoKI2RlZmluZSBwcl92ZWModikgZm9yKGludCBpPTA7aTx2LnNpemUoKTtpKyspIGNvdXQgPDwgdltpXSA8PCAiICIgOwoKI2RlZmluZSBmX2luKHN0KSBmcmVvcGVuKHN0LCJyIixzdGRpbikKI2RlZmluZSBmX291dChzdCkgZnJlb3BlbihzdCwidyIsc3Rkb3V0KQoKI2RlZmluZSBmcihpLCBhLCBiKSBmb3IoaT1hOyBpPD1iOyBpKyspCiNkZWZpbmUgZmIoaSwgYSwgYikgZm9yKGk9YTsgaT49YjsgaS0tKQojZGVmaW5lIEFTU1QoeCwgbCwgcikgYXNzZXJ0KCB4IDw9IHIgJiYgeCA+PSBsICkKCiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+Cgpjb25zdCBpbnQgbW9kID0gMWU5ICsgNzsKCmludCBBREQoaW50IGEsIGludCBiLCBpbnQgbSA9IG1vZCkgewogICAgaW50IHMgPSBhOwogICAgcyArPSBiOwogICAgaWYoIHMgPj0gbSApCiAgICAgIHMgLT0gbTsKICAgIHJldHVybiBzOwp9CgppbnQgTVVMKGludCBhLCBpbnQgYiwgaW50IG0gPSBtb2QpIHsKICAgIHJldHVybiAoMUxMICogYSAqIGIgJSBtKTsKfQoKaW50IHBvd2VyKGludCBhLCBpbnQgYiwgaW50IG0gPSBtb2QpIHsKICAgIGludCByZXMgPSAxOwogICAgd2hpbGUoIGIgKSB7CiAgICAgICAgaWYoIGIgJiAxICkgewogICAgICAgICAgICByZXMgPSAxTEwgKiByZXMgKiBhICUgbTsKICAgICAgICB9CiAgICAgICAgYSA9IDFMTCAqIGEgKiBhICUgbTsKICAgICAgICBiIC89IDI7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgpsbCBuQzIobGwgeCkgewogICAgcmV0dXJuICggeCAqICggeCAtIDEgKSAvIDIgKTsKfQoKY29uc3QgaW50IG1heG4gPSAxZTUgKyA1OwoKaW50IG4sIHE7CnZpIGFkalsgbWF4biBdOwpsbCBjb2xvclsgbWF4biBdOwoKaW50IGdldCggbGwgeCApIHsKCWludCBjID0gMDsKCXdoaWxlKCB4ICkgewoJCWMgKys7CgkJeCAtPSAoeCAmIC14KTsKCX0KCXJldHVybiBjOwp9Cgp2b2lkIGRmcyggaW50IHUsIGludCBwLCBpbnQgaywgaW50IGxldiApIHsKCWlmKCBsZXYgPiBrICkgcmV0dXJuOwoJY29sb3JbIHUgXSA9ICgxTEwgPDwgbGV2KTsKCWZvciggYXV0byBpdDogYWRqW3VdICkgewoJCWlmKCBpdCAhPSBwICkgewoJCQlkZnMoaXQsIHUsIGssIGxldiArIDEpOwoJCX0KCX0KfQoKbGwgcmFuZ2UoaW50IGwsIGludCByKSB7CglsbCBhbnMgPSAwOwoJd2hpbGUoIGwgPD0gciApIHsKCQlhbnMgfD0gY29sb3JbIGwgXTsKCQlsICsrOwoJfQoJcmV0dXJuIGFuczsKfQoKaW50IG1haW4oKSB7CgljaW4gPj4gbiA+PiBxOwoJaW50IGk7CglmcihpLCAxLCBuKSB7CgkJaW50IHgsIHk7CgkJeCA9IGk7IHkgPSAyICogeDsKCQlpZiggeSA8PSBuICkgYWRqW3hdLnBiKCB5ICksIGFkalt5XS5wYiggeCApOwoJCXggPSBpOyB5ID0gMiAqIHggKyAxOwoJCWlmKCB5IDw9IG4gKSBhZGpbeF0ucGIoIHkgKSwgYWRqW3ldLnBiKCB4ICk7Cgl9CgoJd2hpbGUoIHEtLSApIHsKCQlpbnQgdCwgeCwgeSwgazsgc2MxKCB0ICk7CgkJaWYoIHQgPT0gMSApIHsKCQkJc2MyKCB4LCBrICk7IAoJCQlkZnMoIHgsIDAsIGssIDApOwoJCX0gZWxzZSBpZiggdCA9PSAyICkgewoJCQlzYzIoeCwgeSk7CgkJCWxsIGFucyA9IDA7IAoJCQl3aGlsZSggeCAhPSB5ICkgewoJCQkJaWYoIHggPCB5ICkgewoJCQkJCWFucyB8PSBjb2xvclsgeSBdOwoJCQkJCXkgLz0gMjsKCQkJCX0gZWxzZSB7CgkJCQkJYW5zIHw9IGNvbG9yWyB4IF07CgkJCQkJeCAvPSAyOwoJCQkJfQoJCQl9CgkJCWFucyB8PSBjb2xvclsgeCBdOwoJCQlhbnMgLT0gYW5zICUgMjsKCQkJcHIxKCBnZXQoIGFucyApICk7CgkJfSBlbHNlIHsKCQkJc2MxKCB4ICk7CgkJCWludCBsLCByOyBsbCBhbnMgPSAwOwoJCQlsID0gciA9IHg7CgkJCXdoaWxlKCBsIDw9IHIgKSB7CgkJCQlhbnMgfD0gcmFuZ2UobCwgcik7CgkJCQlsICo9IDI7IHIgPSByICogMiArIDE7CgkJCQlyID0gbWluKG4sIHIpOwoJCQl9CgkJCWFucyAtPSBhbnMgJSAyOwoJCQlwcjEoIGdldCggYW5zICkgKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQ==