#include <bits/stdc++.h>

using namespace std;

const int N = 2100010;

using i64 = long long;

const int mod = 1 << 30;

struct Node{
    int l, r, add;
    int sum, key, val;
    int sz, self;
} tr[N];
int n, m;
int root, idx;
int p, q, s;

int new_node(int val, int self) {
    int u = ++idx; 
    tr[u].key = rand();
    tr[u].val = val;
    tr[u].self = self;
    tr[u].sum = 1ll * val * self % mod;
    return u;
}

void add(int& x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

void pushadd(int u, int v) {
    add(tr[u].val, v) %= mod;
    add(tr[u].add, v) %= mod;
    add(tr[u].sum, 1ll * v * tr[u].sz % mod);    
}

void pushdown(int u) {
    if (tr[u].add) {
        pushadd(tr[u].l, tr[u].add);
        pushadd(tr[u].r, tr[u].add);
        tr[u].add = 0;
    }
}

void pushup(int u) {
    tr[u].sum = (tr[tr[u].l].sum + tr[tr[u].r].sum + 1ll * tr[u].self * tr[u].val % mod) % mod;
    tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + tr[u].self;
}

void split(int u, int k, int &x, int &y) {
    if (!u) return x = y = 0, void();
    pushdown(u);
    if (tr[tr[u].l].sz < k) {
        if (tr[tr[u].l].sz + tr[u].self >= k) {
            int lsz = k - tr[tr[u].l].sz;
            int rsz = tr[u].self - lsz;
            x = new_node(tr[u].val, lsz);
            tr[x].l = tr[u].l;
            y = new_node(tr[u].val, rsz);
            tr[y].r = tr[u].r;
            pushup(x), pushup(y);
            return;
        } else {
            x = u;
            split(tr[u].r, k - tr[tr[u].l].sz - tr[u].self, tr[u].r, y);
        }
    } else {
        y = u;
        split(tr[u].l, k, x, tr[u].l);
    }
    pushup(u);
}

int merge(int x, int y) {
    if (!x || !y) return x | y;    
    if (tr[x].key < tr[y].key) {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        return pushup(x), x;
    } else {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        return pushup(y), y;
    }
    assert(false);
    return 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    int M = 1 << m;
    root = idx = 1;
    tr[1].self = M, pushup(1);
    int x = 0;
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        (l += x) %= M, (r += x) %= M;
        ++l, ++r;
        if (l > r) swap(l, r);
        split(root, l - 1, p, q);
        split(q, r - l + 1, q, s);
        pushadd(q, i);
        (x += tr[q].sum) %= mod;
        root = merge(merge(p, q), s);
    }
    cout << x << '\n';
    return 0;
}

answer.code: In function ‘void pushadd(int, int)’:
answer.code:35:8: error: invalid use of ‘void’
   35 |     add(tr[u].val, v) %= mod;
      |     ~~~^~~~~~~~~~~~~~
answer.code:36:8: error: invalid use of ‘void’
   36 |     add(tr[u].add, v) %= mod;
      |     ~~~^~~~~~~~~~~~~~