#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 );
}
int get( ll x ) {
int c = 0;
while( x ) {
c ++;
x -= (x & -x);
}
return c;
}
const int maxn = 1e5 + 5;
int n,m;
ll Tree[4*maxn];
ll Lazy[4*maxn][4];
void adjust(int i,int lo,int hi) {
int mid = (lo+hi) >> 1;
if (Lazy[i][3]!=mod) {
ll x = Lazy[i][3]; Lazy[i][3]=mod;
Tree[2*i] = x; Lazy[2*i][3] = x;
Tree[2*i+1] = x; Lazy[2*i+1][3] = x;
}
}
void update(int i,int lo,int hi,int u,int v,int type,ll x) {
if (v<lo || hi<u) return;
if (u<=lo && hi<=v) {
Tree[i] = x;
Lazy[i][3] = x;
return;
}
int mid = (lo+hi) >> 1;
if (Lazy[i][3]!=mod) adjust(i,lo,hi);
update(2*i,lo,mid,u,v,type,x);
update(2*i+1,mid+1,hi,u,v,type,x);
Tree[i] = (Tree[2*i]|Tree[2*i+1]);
}
ll query(int i,int lo,int hi,int u,int v) {
if (v<lo || hi<u) return 0;
if (u<=lo && hi<=v) return Tree[i];
int mid = (lo+hi) >> 1;
if (Lazy[i][3]!=mod) adjust(i,lo,hi);
return (query(2*i,lo,mid,u,v) | query(2*i+1,mid+1,hi,u,v));
}
void init(int i,int lo,int hi) {
Tree[i]=0;
Lazy[i][3]=mod;
if (lo==hi) return;
int mid = (lo+hi) >> 1;
init(2*i,lo,mid);
init(2*i+1,mid+1,hi);
}
void solve() {
sc2( n, m );
init(1, 1, n);
int t, x, l, r, z, c, y, k, K;
ll ans = 0;
while( m -- ) {
sc1( t );
if( t == 1 ) {
sc2( x, K );
z = x; c = 0;
while( z ) {
if( z != x && c <= K ) {
update(1, 1, n, z, z, 3, (1LL << c));
if( z * 2 == x )
l = r = 2 * z + 1;
else
l = r = 2 * z;
k = c + 1;
} else {
l = r = x;
k = c;
}
r = min(r, n);
while( l <= r && k <= K ) {
update(1, 1, n, l, r, 3, (1LL << k));
k ++; l *= 2; r = r * 2 + 1;
r = min(r, n);
}
x = z;
z = z / 2;
c ++;
}
} else if( t == 2 ) {
sc2(x, y); ans = 0;
while( x != y ) {
if( x < y ) {
ans |= query(1, 1, n, y, y);
y /= 2;
} else {
ans |= query(1, 1, n, x, x);
x /= 2;
}
}
ans |= query(1, 1, n, x, x);
ans -= ans % 2;
pr1( get( ans ) );
} else {
sc1(x);
ans = 0;
l = r = x;
while( l <= r ) {
ans |= query(1, 1, n, l, r);
l *= 2;
r = r * 2 + 1;r = min(r, n);
}
ans -= ans % 2;
pr1( get( ans ) );
}
}
}
int main() {
solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Ci8vICNpbmNsdWRlICJ0ZXN0bGliLmgiICAKdXNpbmcgbmFtZXNwYWNlIHN0ZCA7CgojZGVmaW5lIGZ0IGZpcnN0CiNkZWZpbmUgc2Qgc2Vjb25kCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSx4LmVuZCgpCgojZGVmaW5lIGxsIGxvbmcgbG9uZyBpbnQKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZpaSB2ZWN0b3I8cGFpcjxpbnQsaW50PiA+CiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KI2RlZmluZSBwbGlpIHBhaXI8cGFpcjxsbCwgaW50PiwgaW50PgojZGVmaW5lIHBpaWkgcGFpcjxwaWksIGludD4KI2RlZmluZSB2aWlpIHZlY3RvcjxwYWlyPHBpaSwgaW50PiA+CiNkZWZpbmUgdmwgdmVjdG9yPGxsPgojZGVmaW5lIHZsbCB2ZWN0b3I8cGFpcjxsbCxsbD4gPgojZGVmaW5lIHBsbCBwYWlyPGxsLGxsPgojZGVmaW5lIHBsaSBwYWlyPGxsLGludD4KI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBtcyh4LCB2KSBtZW1zZXQoeCwgdiwgc2l6ZW9mIHgpCgojZGVmaW5lIHNjMSh4KSBzY2FuZigiJWQiLCZ4KQojZGVmaW5lIHNjMih4LHkpIHNjYW5mKCIlZCVkIiwmeCwmeSkKI2RlZmluZSBzYzMoeCx5LHopIHNjYW5mKCIlZCVkJWQiLCZ4LCZ5LCZ6KQoKI2RlZmluZSBzY2xsMSh4KSBzY2FuZigiJWxsZCIsJngpCiNkZWZpbmUgc2NsbDIoeCx5KSBzY2FuZigiJWxsZCVsbGQiLCZ4LCZ5KQojZGVmaW5lIHNjbGwzKHgseSx6KSBzY2FuZigiJWxsZCVsbGQlbGxkIiwmeCwmeSwmeikKCiNkZWZpbmUgcHIxKHgpIHByaW50ZigiJWRcbiIseCkKI2RlZmluZSBwcjIoeCx5KSBwcmludGYoIiVkICVkXG4iLHgseSkKI2RlZmluZSBwcjMoeCx5LHopIHByaW50ZigiJWQgJWQgJWRcbiIseCx5LHopCgojZGVmaW5lIHBybGwxKHgpIHByaW50ZigiJWxsZFxuIix4KQojZGVmaW5lIHBybGwyKHgseSkgcHJpbnRmKCIlbGxkICVsbGRcbiIseCx5KQojZGVmaW5lIHBybGwzKHgseSx6KSBwcmludGYoIiVsbGQgJWxsZCAlbGxkXG4iLHgseSx6KQoKI2RlZmluZSBwcl92ZWModikgZm9yKGludCBpPTA7aTx2LnNpemUoKTtpKyspIGNvdXQgPDwgdltpXSA8PCAiICIgOwoKI2RlZmluZSBmX2luKHN0KSBmcmVvcGVuKHN0LCJyIixzdGRpbikKI2RlZmluZSBmX291dChzdCkgZnJlb3BlbihzdCwidyIsc3Rkb3V0KQoKI2RlZmluZSBmcihpLCBhLCBiKSBmb3IoaT1hOyBpPD1iOyBpKyspCiNkZWZpbmUgZmIoaSwgYSwgYikgZm9yKGk9YTsgaT49YjsgaS0tKQojZGVmaW5lIEFTU1QoeCwgbCwgcikgYXNzZXJ0KCB4IDw9IHIgJiYgeCA+PSBsICkKCiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+Cgpjb25zdCBpbnQgbW9kID0gMWU5ICsgNzsKCmludCBBREQoaW50IGEsIGludCBiLCBpbnQgbSA9IG1vZCkgewogICAgaW50IHMgPSBhOwogICAgcyArPSBiOwogICAgaWYoIHMgPj0gbSApCiAgICAgIHMgLT0gbTsKICAgIHJldHVybiBzOwp9CgppbnQgTVVMKGludCBhLCBpbnQgYiwgaW50IG0gPSBtb2QpIHsKICAgIHJldHVybiAoMUxMICogYSAqIGIgJSBtKTsKfQoKaW50IHBvd2VyKGludCBhLCBpbnQgYiwgaW50IG0gPSBtb2QpIHsKICAgIGludCByZXMgPSAxOwogICAgd2hpbGUoIGIgKSB7CiAgICAgICAgaWYoIGIgJiAxICkgewogICAgICAgICAgICByZXMgPSAxTEwgKiByZXMgKiBhICUgbTsKICAgICAgICB9CiAgICAgICAgYSA9IDFMTCAqIGEgKiBhICUgbTsKICAgICAgICBiIC89IDI7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgpsbCBuQzIobGwgeCkgewogICAgcmV0dXJuICggeCAqICggeCAtIDEgKSAvIDIgKTsKfQoKaW50IGdldCggbGwgeCApIHsKCWludCBjID0gMDsKCXdoaWxlKCB4ICkgewoJCWMgKys7CgkJeCAtPSAoeCAmIC14KTsKCX0KCXJldHVybiBjOwp9Cgpjb25zdCBpbnQgbWF4biA9IDFlNSArIDU7CgppbnQgbixtOwpsbCBUcmVlWzQqbWF4bl07CmxsIExhenlbNCptYXhuXVs0XTsKCnZvaWQgYWRqdXN0KGludCBpLGludCBsbyxpbnQgaGkpIHsKICAgIGludCBtaWQgPSAobG8raGkpID4+IDE7CiAgICBpZiAoTGF6eVtpXVszXSE9bW9kKSB7CiAgICAgICAgbGwgeCA9IExhenlbaV1bM107IExhenlbaV1bM109bW9kOwogICAgICAgIFRyZWVbMippXSA9IHg7IExhenlbMippXVszXSA9IHg7CiAgICAgICAgVHJlZVsyKmkrMV0gPSB4OyBMYXp5WzIqaSsxXVszXSA9IHg7CiAgICB9Cn0KCnZvaWQgdXBkYXRlKGludCBpLGludCBsbyxpbnQgaGksaW50IHUsaW50IHYsaW50IHR5cGUsbGwgeCkgewogICAgaWYgKHY8bG8gfHwgaGk8dSkgcmV0dXJuOwogICAgaWYgKHU8PWxvICYmIGhpPD12KSB7CiAgICAgICAgVHJlZVtpXSA9IHg7CiAgICAgICAgTGF6eVtpXVszXSA9IHg7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IG1pZCA9IChsbytoaSkgPj4gMTsKICAgIGlmIChMYXp5W2ldWzNdIT1tb2QpIGFkanVzdChpLGxvLGhpKTsKICAgIHVwZGF0ZSgyKmksbG8sbWlkLHUsdix0eXBlLHgpOwogICAgdXBkYXRlKDIqaSsxLG1pZCsxLGhpLHUsdix0eXBlLHgpOwogICAgVHJlZVtpXSA9IChUcmVlWzIqaV18VHJlZVsyKmkrMV0pOwp9CgpsbCBxdWVyeShpbnQgaSxpbnQgbG8saW50IGhpLGludCB1LGludCB2KSB7CiAgICBpZiAodjxsbyB8fCBoaTx1KSByZXR1cm4gMDsKICAgIGlmICh1PD1sbyAmJiBoaTw9dikgcmV0dXJuIFRyZWVbaV07CiAgICBpbnQgbWlkID0gKGxvK2hpKSA+PiAxOwogICAgaWYgKExhenlbaV1bM10hPW1vZCkgYWRqdXN0KGksbG8saGkpOwogICAgcmV0dXJuIChxdWVyeSgyKmksbG8sbWlkLHUsdikgfCBxdWVyeSgyKmkrMSxtaWQrMSxoaSx1LHYpKTsKfQoKdm9pZCBpbml0KGludCBpLGludCBsbyxpbnQgaGkpIHsKICAgIFRyZWVbaV09MDsKICAgIExhenlbaV1bM109bW9kOwogICAgaWYgKGxvPT1oaSkgcmV0dXJuOwogICAgaW50IG1pZCA9IChsbytoaSkgPj4gMTsKICAgIGluaXQoMippLGxvLG1pZCk7CiAgICBpbml0KDIqaSsxLG1pZCsxLGhpKTsKfQoKdm9pZCBzb2x2ZSgpIHsKCXNjMiggbiwgbSApOwoJaW5pdCgxLCAxLCBuKTsKCWludCB0LCB4LCBsLCByLCB6LCBjLCB5LCBrLCBLOwoJbGwgYW5zID0gMDsKCXdoaWxlKCBtIC0tICkgewoJCXNjMSggdCApOwoJCWlmKCB0ID09IDEgKSB7CgkJCXNjMiggeCwgSyApOwoJCQl6ID0geDsgYyA9IDA7CgkJCXdoaWxlKCB6ICkgewoJCQkJaWYoIHogIT0geCAmJiBjIDw9IEsgKSB7CgkJCQkJdXBkYXRlKDEsIDEsIG4sIHosIHosIDMsICgxTEwgPDwgYykpOwoJCQkJCWlmKCB6ICogMiA9PSB4ICkKCQkJCQkJbCA9IHIgPSAyICogeiArIDE7CgkJCQkJZWxzZSAKCQkJCQkJbCA9IHIgPSAyICogejsKCQkJCQlrID0gYyArIDE7CgkJCQl9IGVsc2UgewoJCQkJCWwgPSByID0geDsKCQkJCQlrID0gYzsKCQkJCX0KCQkJCXIgPSBtaW4ociwgbik7CgkJCQl3aGlsZSggbCA8PSByICYmIGsgPD0gSyApIHsKCQkJCQl1cGRhdGUoMSwgMSwgbiwgbCwgciwgMywgKDFMTCA8PCBrKSk7CgkJCQkJayArKzsgbCAqPSAyOyByID0gciAqIDIgKyAxOwoJCQkJCXIgPSBtaW4ociwgbik7IAoJCQkJfQoJCQkJeCA9IHo7CgkJCQl6ID0geiAvIDI7CgkJCQljICsrOwoJCQl9CgkJfSBlbHNlIGlmKCB0ID09IDIgKSB7CgkJCXNjMih4LCB5KTsgYW5zID0gMDsKCQkJd2hpbGUoIHggIT0geSApIHsKCQkJCWlmKCB4IDwgeSApIHsKCQkJCQlhbnMgfD0gcXVlcnkoMSwgMSwgbiwgeSwgeSk7CgkJCQkJeSAvPSAyOwoJCQkJfSBlbHNlIHsKCQkJCQlhbnMgfD0gcXVlcnkoMSwgMSwgbiwgeCwgeCk7CgkJCQkJeCAvPSAyOwoJCQkJfQoJCQl9CgkJCWFucyB8PSBxdWVyeSgxLCAxLCBuLCB4LCB4KTsKCQkJYW5zIC09IGFucyAlIDI7CgkJCXByMSggZ2V0KCBhbnMgKSApOwoJCX0gZWxzZSB7CgkJCXNjMSh4KTsKCQkJYW5zID0gMDsKCQkJbCA9IHIgPSB4OwoJCQl3aGlsZSggbCA8PSByICkgewoJCQkJYW5zIHw9IHF1ZXJ5KDEsIDEsIG4sIGwsIHIpOwoJCQkJbCAqPSAyOwoJCQkJciA9IHIgKiAyICsgMTtyID0gbWluKHIsIG4pOwoJCQl9CgkJCWFucyAtPSBhbnMgJSAyOwoJCQlwcjEoIGdldCggYW5zICkgKTsKCQl9Cgl9Cn0KCgppbnQgbWFpbigpIHsKCXNvbHZlKCk7CglyZXR1cm4gMDsKfQ==