#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cerr << #x << ": " << x << el
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 5e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

struct Node {
    int lc, rc;
    int l, r;
    int rnd;
    int sz, v, s, add;
    void init(int _l, int _r, int _v) {
        lc = rc = 0, l = _l, r = _r, rnd = rand(), sz = r - l + 1, v = _v, s = v * sz;
    }
}tr[N * 3];
int idx;

void pushup(int u) {
    tr[u].s = tr[tr[u].lc].s + tr[tr[u].rc].s + tr[u].v * (tr[u].r - tr[u].l + 1);
    tr[u].sz = tr[tr[u].lc].sz + tr[tr[u].rc].sz + tr[u].r - tr[u].l + 1;
}

void pushdown(int u) {
    auto &p = tr[u], &lc = tr[tr[u].lc], &rc = tr[tr[u].rc];
    if (p.add) {
        lc.add += p.add, lc.v += p.add, lc.s += p.add * lc.sz;
        rc.add += p.add, rc.v += p.add, rc.s += p.add * rc.sz;
        p.add = 0;
    }
}

void split(int p, int k, int &x, int &y) {
    if (!p) x = y = 0;
    else {
        pushdown(p);
        if (tr[p].l <= k) {
            x = p;
            split(tr[p].rc, k, tr[p].rc, y);
        }
        else {
            y = p;
            split(tr[p].lc, k, x, tr[p].lc);
        }
        pushup(p);
    }
}

int merge(int p, int q) {
    if (!p || !q) return p + q;
    else if (tr[p].rnd > tr[q].rnd) {
        pushdown(p);
        tr[p].rc = merge(tr[p].rc, q);
        pushup(p);
        return p;
    }
    else {
        pushdown(q);
        tr[q].lc = merge(p, tr[q].lc);
        pushup(q);
        return q;
    }
}

void pushtag(int p, int add) {
    tr[p].v += add, tr[p].s += add * tr[p].sz, tr[p].add += add;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    int last = 0, v = (1 << m) - 1;
    tr[++idx].init(0, v, 0);
    int root = 1;
    for (int i = 1; i <= n; ++i) {
        int l, r; cin >> l >> r;
        l = l + last & v, r = r + last & v;
        if (l > r) swap(l, r);
        int x, y, z, a;
        split(root, l, y, z);
        int p = y; while (tr[p].rc) p = tr[p].rc;
        split(y, tr[p].l - 1, x, y);
        if (tr[y].l != l) {
            tr[++idx].init(l, tr[y].r, tr[y].v);
            tr[y].init(tr[y].l, l - 1, tr[y].v);
            x = merge(x, y);
            y = idx;
        }
        y = merge(y, z);
        if (r == v) {
            pushtag(y, i);
            last += tr[y].s;
            root = merge(x, y);
            continue;
        }
        split(y, r + 1, y, z);
        p = y; while (tr[p].rc) p = tr[p].rc;
        split(y, tr[p].l - 1, a, y);
        if (tr[y].l != r + 1) {
            tr[++idx].init(r + 1, tr[y].r, tr[y].v);
            tr[y].init(tr[y].l, r, tr[y].v);
            y = merge(a, y), z = merge(idx, z);
        }
        pushtag(y, i);
        last += tr[y].s;
        root = merge(merge(x, y), z);
    }
    cout << (last & (1 << 30) - 1) << el;
}