descompunere

#include <fstream>

using namespace std;

ifstream cin("descompunere.in");
ofstream cout("descompunere.out");

typedef long long ll;

ll ln, cl, ans;

void solve(ll l1, ll c1, ll l2, ll c2, ll l3, ll c3, int in){
    int mdL;

    if(in == 1)
        mdL = (l1 + l2) / 2;
    else
        mdL = (l1 + l3) / 2;

    if(mdL == l1){
        if(in == 1){
            if(ln == l1 && cl == c1)
                ans += 0;
            else if(ln == l2 && cl == c2)
                ans += 1;
            else if(ln == l3 && cl == c3)
                ans += 3;
            else
                ans += 2;
        } else {
            if(ln == l1 && cl == c1)
                ans += 1;
            else if(ln == l2 && cl == c2)
                ans += 3;
            else if(ln == l3 && cl == c3)
                ans += 0;
            else
                ans += 2;
        }
    } else {
        if(in == 1){
            if(l1 <= ln && ln <= mdL){
                ans += 0;
                solve(l1, c1, mdL, c1, mdL, mdL * 2 - 1, 1);
            } else if(ln >= mdL + 1){
                ll lvl = (ln - mdL);
                ll cL = c2 + (lvl * 2 - 1) - 1;
                ll cR = c3 - (lvl * 2 - 1) + 1;

                if(cl <= cL){
                    ans += 1;
                    solve(mdL + 1, c1, l2, c2, l2, cL, 1);
                } else if(cl >= cR){
                    ans += 3;
                    solve(mdL + 1, cR, l2, cR, l2, c3, 1);
                } else {
                    ans += 2;
                    solve(mdL + 1, c1 + 1, mdL + 1, cR - 1, l2, cL + 1, -1);
                }
            }
        } else {
            if(mdL + 1 <= ln && ln <= l3){
                ans += 0;
                ll lvl = (l3 - l1 + 1) / 2;
                solve(mdL + 1, c3 - (lvl * 2 - 1) + 1, mdL + 1, c3, l3, c3, -1);
            } else {
                ll cL = c2 / 2;

                if(cl <= cL){
                    ans += 1;
                    solve(l1, c1, l2, cL, mdL, cL, -1);
                } else {
                    ll lvl = ln - l1 + 1;
                    int cR = cL + 1 + (lvl * 2 - 1) - 1;

                    if(cl <= cR){
                        ans += 2;
                        solve(l1, cL + 1, mdL, cL + 1, mdL, c2 - 1, 1);
                    } else {
                        ans += 3;
                        solve(l1, cL + 2, l1, c2, mdL, c2, -1);
                    }
                }
            }
        }
    }
}

int main()
{
    int n, m;

    cin >> n >> m;

    while(m--){
        ans = 0;
        cin >> ln >> cl;

        solve(1, 1, (1LL << n), 1, (1LL << n), (1LL << (n + 1)) - 1, 1);

        cout << ans << "\n";
    }

    return 0;
}