#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

const int N = 2e6 + 7;

unsigned int Mod;

struct uint
{
    unsigned int val;
    uint() : val(0) {}
    uint(int x) : val(x) {}
    operator bool() const { return val != 0; }
    uint operator+(const uint &X) const
    {
        uint tmp(val + X.val);
        if (tmp.val >= Mod)
            tmp.val -= Mod;
        return tmp;
    }
    uint operator-(const uint &X) const
    {
        uint tmp(val - X.val);
        if (tmp.val < 0)
            tmp.val += Mod;
        return tmp;
    }
    uint operator*(const uint &X) const
    {
        return uint(1ull * val * X.val % Mod);
    }
    const uint &operator+=(const uint &X)
    {
        val += X.val;
        if (val >= Mod)
            val -= Mod;
        return (*this);
    }
    bool operator<(const uint &X) const
    {
        return val < X.val;
    }
    explicit operator int() const
    {
        return val;
    }
};

istream &operator>>(istream &os, uint &X)
{
    return os >> X.val;
}

ostream &operator<<(ostream &os, uint &X)
{
    return os << X.val;
}

struct Node
{
    uint Sum, val, tag;
    int ls, rs, key;
    int l, r, L, R;
} t[N];

int NewNode(int l, int r, uint val)
{
    static int cnt = 0;
    t[++cnt] = (Node){0, val, 0, 0, 0, rand(), l, r, l, r};
    t[cnt].Sum = uint(r - l + 1) * t[cnt].val;
    return cnt;
}

void update(int id)
{
    t[id].L = t[id].ls ? t[t[id].ls].L : t[id].l;
    t[id].R = t[id].rs ? t[t[id].rs].R : t[id].r;
    t[id].Sum = t[t[id].ls].Sum + t[t[id].rs].Sum + t[id].val * uint(t[id].r - t[id].l + 1);
}

void add(int id, uint val)
{
    t[id].val += val;
    t[id].Sum += val * uint(t[id].R - t[id].L + 1);
    t[id].tag += val;
}

void pd(int id)
{
    if (!t[id].tag)
        return;
    if (t[id].ls)
        add(t[id].ls, t[id].tag);
    if (t[id].rs)
        add(t[id].rs, t[id].tag);
    t[id].tag = 0;
}

int merge(int x, int y)
{
    if (!x || !y)
        return x | y;
    if (t[x].key <= t[y].key)
    {
        pd(x);
        t[x].rs = merge(t[x].rs, y);
        return update(x), x;
    }
    else
    {
        pd(y);
        t[y].ls = merge(x, t[y].ls);
        return update(y), y;
    }
}

void split(int id, int k, bool op, int &x, int &y)
{
    if (!id)
        x = y = 0;
    else
    {
        pd(id);
        if ((!op && t[id].l <= k) || (op && t[id].r <= k))
            x = id, split(t[x].rs, k, op, t[x].rs, y);
        else
            y = id, split(t[y].ls, k, op, x, t[y].ls);
        update(id);
    }
}

int n, m, rt;

void Split(int l, int r, int &x, int &y, int &z)
{
    x = y = z = 0;
    split(rt, l - 1, 0, x, y);
    split(y, r, 1, y, z);
    int now = x;
    while (t[now].rs)
        now = t[now].rs;
    if (now && t[now].r > r)
    {
        y = NewNode(l, r, t[now].val);
        z = merge(NewNode(r + 1, t[now].r, t[now].val), z);
        t[now].r = l - 1;
        update(now);
    }
    else
    {
        if (now && t[now].r >= l)
        {
            y = merge(NewNode(l, t[now].r, t[now].val), y);
            t[now].r = l - 1;
            update(now);
        }
        now = z;
        while (t[now].ls)
            now = t[now].ls;
        if (now && t[now].l <= r)
        {
            y = merge(y, NewNode(t[now].l, r, t[now].val));
            t[now].l = r + 1;
            update(now);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    srand(114514);
    cin >> n >> m;
    m = 1 << m;
    Mod = 1 << 30;
    rt = NewNode(0, m - 1, 0);
    int p, q = 0;
    uint X = 0;
    int x, y, z;
    for (int i = 1; i <= n; i++)
    {
        cin >> p >> q;
        p += int(X), q += int(X);
        p %= m, q %= m;
        if (p > q)
            swap(p, q);
        Split(p, q, x, y, z);
        add(y, i);
        X += t[y].Sum;
        rt = merge(merge(x, y), z);
    }
    cout << X;
}

answer.code:11:8: error: using typedef-name ‘uint’ after ‘struct’
   11 | struct uint
      |        ^~~~
In file included from /usr/include/stdlib.h:394,
                 from /usr/include/c++/13/cstdlib:79,
                 from /usr/include/c++/13/ext/string_conversions.h:43,
                 from /usr/include/c++/13/bits/basic_string.h:4097,
                 from /usr/include/c++/13/string:54,
                 from /usr/include/c++/13/bits/locale_classes.h:40,
                 from /usr/include/c++/13/bits/ios_base.h:41,
                 from /usr/include/c++/13/ios:44,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/sys/types.h:150:22: note: ‘uint’ has a previous declaration here
  150 | typedef unsigned int uint;
      |                      ^~~~
answer.code: In function ‘std::istream& operator>>(std::istream&, uint&)’:
answer.code:54:20: error: request for member ‘val’ in ‘X’, which is of non-class type ‘uint’ {aka ‘unsigned int’}
   54 |     return os >> X.val;
      |                    ^~~
answer.code: In function ‘std::ostream& operator<<(std::ostream&, uint&)’:
answer.code:59:20: error: request for member ‘val’ in ‘X’, which is of non-class type ‘uint’ {aka ‘unsigned int’}
   59 |     return os << X.val;
      |                    ^~~
answer.code: In function ‘int main()’:
answer.code:195:10: error: ambiguous overload for ‘operator<<’ (operand types are ‘std::ostream’ {aka ‘std::basic_ostream<char>’} and ‘uint’ {aka ‘unsigned int’})
  195 |     cout << X;
      |     ~~~~ ^~ ~
      |     |       |
      |     |       uint {aka unsigned int}
      |     std::ostream {aka std::basic_ostream<char>}
/usr/include/c++/13/ostream:168:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  168 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:172:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  172 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:176:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  176 |       operator<<(bool __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/13/ostream:880:
/usr/include/c++/13/bits/ostream.tcc:96:5: note: candidate: ‘std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]’
   96 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/ostream:183:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  183 |       operator<<(unsigned short __n)
      |       ^~~~~~~~
/usr/include/c++/13/bits/ostream.tcc:110:5: note: candidate: ‘std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]’
  110 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/ostream:194:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  194 |       operator<<(unsigned int __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:203:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  203 |       operator<<(long long __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:207:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
  207 |       operator<<(unsigned long long __n)
      |       ^~~~~~~~
/usr/include/c++/13/ostream:222:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<...