#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int unsigned
using namespace std;

const int N = 1e6 + 10, mod = 1 << 30;
int n, m, all, tot, root;
mt19937 rnd(time(0));
int siz[N], w[N], ch[N][2], b[N];
int tree_siz[N], val[N], sum[N], tag[N], x;
int newnode(int x, int s, int l)
{
    int ret = ++tot;
    b[ret] = l;
    val[ret] = x, siz[ret] = s;
    tree_siz[ret] = s;
    sum[ret] = x * s;
    return ret;
}
void pushdown(int cur)
{
    if (!tag[cur])
        return;
    if (int lc = ch[cur][0]; lc)
    {
        tag[lc] += tag[cur];
        sum[lc] += tree_siz[lc] * tag[cur];
        val[lc] += tag[cur];
    }
    if (int rc = ch[cur][1]; rc)
    {
        tag[rc] += tag[cur];
        sum[rc] += tree_siz[rc] * tag[cur];
        val[rc] += tag[cur];
    }
    tag[cur] = 0;
}
void pushup(int cur)
{
    tree_siz[cur] = siz[cur] + tree_siz[ch[cur][0]] + tree_siz[ch[cur][1]];
    sum[cur] = val[cur] * siz[cur] + sum[ch[cur][0]] + sum[ch[cur][1]];
}
int merge(int x, int y)
{
    if (!x or !y)
        return x | y;

    pushdown(x), pushdown(y);
    int ret;
    if (w[x] < w[y])
    {
        ch[x][1] = merge(ch[x][1], y);
        ret = x;
    }
    else
    {
        ch[y][0] = merge(x, ch[y][0]);
        ret = y;
    }
    pushup(ret);
    return ret;
}
pair<int, int> split(int x, int z)
{
    if (!x)
        return {0, 0};

    pushdown(x);
    if (b[x] <= z and z < b[x] + siz[x] - 1)
    {
        int cur = newnode(val[x], siz[x] - (z + 1 - b[x]), z + 1);
        siz[x] = z + 1 - b[x];
        cur = merge(cur, ch[x][1]);
        ch[x][1] = 0;
        pushup(x);
        return {x, cur};
    }

    pair<int, int> ret;
    if (z < b[x])
    {
        ret = split(ch[x][0], z);
        ch[x][0] = ret.second;
        ret.second = x;
    }
    else
    {
        ret = split(ch[x][1], z);
        ch[x][1] = ret.first;
        ret.first = x;
    }
    pushup(x);
    return ret;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n * 2 + 1; i++)
        w[i] = rnd();
    all = 1 << m;
    root = newnode(0, all, 0);

    for (int i = 1, p, q; i <= n; i++)
    {
        cin >> p >> q;
        p = (p + x) % all, q = (q + x) % all;
        if (p > q)
            swap(p, q);

        auto r1 = split(root, p - 1);
        auto r2 = split(r1.second, q);
        tag[r2.first] += i;
        val[r2.first] += i;
        sum[r2.first] += tree_siz[r2.first] * i;
        x += sum[r2.first];
        root = merge(r1.first, merge(r2.first, r2.second));
    }
    cout << x << '\n';
}
/*
 5 2
 2 1
 1 3
 3 2
 1 0
 0 2
*/