#include<bits/stdc++.h>
using namespace std;
mt19937 mt(time(0));
constexpr int M=1e6+5;
int n,m,lim,ans,num,rt;
struct Treap{
    int ls,rs,val;
    unsigned int sum1,sum2,val1,val2,rnd;
}tr[M];
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
void pushup(int x){
    tr[x].sum1=tr[tr[x].ls].sum1+tr[tr[x].rs].sum1+tr[x].val1;
    tr[x].sum2=tr[tr[x].ls].sum2+tr[tr[x].rs].sum2+tr[x].val2;
}
void split(int now,int k,int &x,int &y){
    if (!now) return x=y=0,void();
    if (tr[now].val<=k) x=now,split(tr[x].rs,k,tr[x].rs,y);
    else y=now,split(tr[y].ls,k,x,tr[y].ls); pushup(now);
}
int merge(int x,int y){
    if (!x||!y) return x|y;
    if (tr[x].rnd<tr[y].rnd){
        tr[x].rs=merge(tr[x].rs,y);
        return pushup(x),x;
    }
    tr[y].ls=merge(x,tr[y].ls);
    return pushup(y),y;
}
int new_node(unsigned int a,unsigned int b,int k){
    tr[++num].val=k;tr[num].rnd=mt();
    tr[num].sum1=tr[num].val1=a;
    tr[num].sum2=tr[num].val2=b;
    return num;
}
void insert(int p,int c){
    int x,y; split(rt,p,x,y); 
    rt=merge(merge(x,new_node(1u*c,1u*p*c,p)),y);
}
unsigned int getans(int l,int r){
    int x,y,z;
    split(rt,r,x,z);
    unsigned int ansr=(r+1)*tr[x].sum1-tr[x].sum2;
    split(x,l-1,x,y);
    unsigned int ansl=l*tr[x].sum1-tr[x].sum2;
    rt=merge(merge(x,y),z);return ansr-ansl;
}
int main(){
    n=read();m=read();lim=1<<m;
    for (int i=1;i<=n;i++){
        int l=read(),r=read();
        l=(l+ans)%lim;r=(r+ans)%lim;
        if (l>r) swap(l,r);
        insert(l,i);insert(r+1,-i);
        ans+=getans(l,r);
    }
    printf("%d\n",ans%(1<<30));
    return 0;
}