Let’s play a game.We add numbers 1,2...n in increasing order from 1 and put them into some sets. 
When we add i,we must create a new set, and put iinto it.And meanwhile we have to bring [i-lowbit(i)+1,i-1] from their original sets, and put them into the new set,too.When we put one integer into a set,it costs us one unit physical strength. But bringing integer from old set does not cost any physical strength. 
After we add 1,2...n,we have q queries now.There are two different kinds of query: 
1 L R:query the cost of strength after we add all of [L,R](1≤L≤R≤n) 
2 x:query the units of strength we cost for putting x(1≤x≤n) into some sets. 

InputThere are several cases,process till end of the input. 
For each case,the first line contains two integers n and q.Then q lines follow.Each line contains one query.The form of query has been shown above. 
n≤10^18,q≤10^5 
OutputFor each query, please output one line containing your answer for this querySample Input

10 2

1 8 9

2 6

Sample Output

9

2

Hint

lowbit(i) =i&(-i).It means the size of the lowest nonzero bits in binary of i. For example, 610=1102, lowbit(6) =102= 210

When we add 8,we should bring [1,7] and 8 into new set.

When we add 9,we should bring [9,8] (empty) and 9 into new set.

So the first answer is 8+1=9.

When we add 6 and 8,we should put 6 into new sets.

So the second answer is 2. 

题意：
多组输入，。每一组数据，有一个数字n，和一个数q，
有1~n个数，将i放入集合中同时放入i-lowbit(i)+1~ i 的所有数。
每向集合中放入一个数，就会消耗一点体力值。

然后有q个询问，询问1是，给你一个l和r，问l~r每一个数都加入到集合中，会消耗多少体力值。
2.
1~n中，对每一个数进行加入到集合中的话，数x会被加入多少次。

思路：
把i放入集合就会放入i-lowbit(i)+1~i的所有数
那么一共就是加入i - (i-lowbit(i)+1) +1 个数，即lowbit(i)个数，
那么一个数i消耗的体力值就是lowbit（i）
那么第一问就是让求l~r的lowbit的sum和。

由于数据量很大，我们不能扫一遍算出，
那么我们来分析一下是否可以优化。，
我们知道，lowbit(i)表示的是数字i的二进制最低位代表的十进制数。
例如6的二进制是110，最低位时第2个1，从右向左第2位，代表的十进制时2，（二进制10是十进制的2），那么lowbit（6）就是2。
那么l~r的lowbit的sum和就是，最低位的1在0位置上的数的数量*1（代表的十进制）+ 最低位的1在1位置上的数的数量*2 +.....
那么问题转化为如何快速的求出l~r中最低位的1在第i位的数的数量，
我们知道这样的一个求解方法（容斥的思想）n/(1<<P)-n/(1<<(p+1))就是·1~n中最低位的1在第p位（从右向左数，0开始计位）的数的数量。
那么我们只需要logn来枚举每一位，然后上面的公式即可计算出每一位的数量。

然后我们来看第二个问题，
要找到x在几个集合中，可用x=x+lowbit（x）找出有多少满足条件的x，就能得到集合的个数

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define dll(x) scanf("%I64d",&x)

#define xll(x) printf("%I64d\n",x)

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll powmod(ll a,ll b,ll MOD){ll ans=;while(b){if(b%)ans=ans*a%MOD;a=a*a%MOD;b/=;}return ans;}

inline void getInt(int* p);

const int maxn=;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll solve(ll x)

{

    ll res=0ll;

    for(ll p=1ll;p<=x;p<<=)

    {

        res+=(x/p-x/(p<<))*p;

    }

    return res;

}

ll lowbit(ll x)

{

    return x&(-x);

}

ll solve2(ll x,ll n)

{

    ll res=0ll;

    while(x<=n)

    {

        res++;

        x+=lowbit(x);

    }

    return res;

}

int main()

{

    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);

    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);

    ll n,q;

    while(~scanf("%lld %lld",&n,&q))

    {

        int op;

        while(q--)

        {

            scanf("%d",&op);

            if(op==)

            {

                ll l,r;

                scanf("%lld %lld",&l,&r);

                ll res=solve(r)-solve(l-1ll);

                printf("%lld\n",res );

            }else

            {

                ll x;

                scanf("%lld",&x);

                printf("%lld\n",solve2(x,n) );

            }

        }

    }

    return ;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '');

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  - ch + '';

        }

    }

    else {

        *p = ch - '';

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  + ch - '';

        }

    }

}