#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int unsigned
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back

struct Op
{
    int add;
    static Op noop()
    {
        return {0};
    }
    void apply(Op upd)
    {
        add+=upd.add;
    }
};

struct Val
{
    int sum;
    static Val range(int lo,int hi)
    {
        return {0};
    }
    static Val empty()
    {
        return {0};
    }
    static Val combine(Val l,Val r)
    {
        return {l.sum+r.sum};
    }
    void apply(Op upd,int lo,int hi)
    {
        sum+=(hi-lo)*upd.add;
    }
};

struct Node {
    Node* l=0,*r=0;
    int lo, hi; Val val; Op op = Op::noop();
    Node(int lo, int hi) // implicit segment tree
            : lo(lo), hi(hi), val(Val::range(lo, hi)) {}
    Val query(int L, int R) {
        if (R <= lo || hi <= L) return Val::empty();
        if (L <= lo && hi <= R) return val;
        push();
        return Val::combine(l->query(L, R), r->query(L, R));
    }
    void update(int L, int R, Op upd) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) val.apply(upd,lo,hi), op.apply(upd);
        else {
            push(), l->update(L, R, upd), r->update(L, R, upd);
            val = Val::combine(l->val, r->val);
        }
    }
    void push() {
        if (!l) { // only for implicit segment tree
            int mid = lo + (hi - lo) / 2;
            l = new Node(lo, mid); r = new Node(mid, hi);
        }
        l->update(lo, hi, op); r->update(lo, hi, op);
        op = Op::noop();
    }
    ~Node()
    {
        delete l;
        delete r;
    }
};

const int M=30,LEN=1<<M,MASK=LEN-1;

int n0 = 1;
vector<tuple<signed,unsigned,unsigned > > upd = { {-1,0, 0} };

void quer(int l, int r, int x)
{
//    cout<<"quer "<<l<<" "<<r<<" "<<x<<"\n";
    upd.pb({r+1, 0-x, 0});
    upd.pb({l, x, 0});
}
void process()
{
    for (signed i=n0-2; i>=0; i--)
        get<1>(upd[i+1]) -= get<1>(upd[i]);
//    cout<<"process"<<"\n";
    n0 = upd.size();
    sort(upd.begin(), upd.end());
    for (int i=0; i+1<n0; i++)
        get<1>(upd[i+1]) += get<1>(upd[i]);
    for (int i=1; i<n0; i++)
    {
        get<2>(upd[i]) = get<1>(upd[i-1]) * (get<0>(upd[i]) - get<0>(upd[i-1]));
    }
    for (int i=1; i<n0; i++)
        get<2>(upd[i]) += get<2>(upd[i-1]);
//    for(auto[x,y,z]:upd)
//        cout<<"("<<x<<","<<y<<","<<z<<") ";
//    cout<<"\n";
}
int ask(int r)
{
    auto it = lower_bound(upd.begin(), upd.begin() + n0, tuple<signed,unsigned,unsigned>{r+1, 0, 0});
    it = prev(it);
    int i = it-upd.begin();
//    cout<<"ask "<<r<<" -> "<<get<2>(upd[i]) + get<1>(upd[i]) * (r - get<0>(upd[i]))<<"\n";
    return get<2>(upd[i]) + get<1>(upd[i]) * (r - get<0>(upd[i]) + 1);
}
const int BLOCK=5e4;
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n=5e5,m=30;
    cin>>n>>m;
    int len=1<<m,mask=len-1;
    auto*tree=new Node(0,len);
    int x=0;
    mt19937 rng;
    upd.reserve(2*n+10);
    for(int i=1;i<=n;i++)
    {
        if(i%BLOCK==0) {
            process();
            delete tree;
            tree=new Node(0,len);
        }
        int l=rng(),r=rng();
        cin>>l>>r;
        l+=x,r+=x;
        l&=mask,r&=mask;
        if(l>r) swap(l,r);
        tree->update(l,r+1,{i});
        quer(l,r,i);
        x+=tree->query(l,r+1).sum+ask(r)-(l?ask(l-1):0);
    }
//    vector<pii> segs;
//    tree->dfs(segs);
    cout<<(x&MASK);
}