#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


// fast IO by yosupo
// sc.read(string &) appends the input
struct Scanner {
    FILE* fp = nullptr;
    char line[(1 << 15) + 1];
    size_t st = 0, ed = 0;
    void reread() {
        memmove(line, line + st, ed - st);
        ed -= st;
        st = 0;
        ed += fread(line + ed, 1, (1 << 15) - ed, fp);
        line[ed] = '\0';
    }
    bool succ() {
        while (true) {
            if (st == ed) {
                reread();
                if (st == ed) return false;
            }
            while (st != ed && isspace(line[st])) st++;
            if (st != ed) break;
        }
        if (ed - st <= 50) reread();
        return true;
    }
    template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        while (true) {
            size_t sz = 0;
            while (st + sz < ed && !isspace(line[st + sz])) sz++;
            ref.append(line + st, sz);
            st += sz;
            if (!sz || st != ed) break;
            reread();            
        }
        return true;
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        ref = T(0);
        while (isdigit(line[st])) {
            ref = 10 * ref + (line[st++] - '0');
        }
        if (neg) ref = -ref;
        return true;
    }
    template <class T> bool read_single(vector<T>& ref) {
        for (auto& d : ref) {
            if (!read_single(d)) return false;
        }
        return true;
    }
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
    Scanner(FILE* _fp) : fp(_fp) {}
};

struct Printer {
  public:
    template <bool F = false> void write() {}
    template <bool F = false, class H, class... T>
    void write(const H& h, const T&... t) {
        if (F) write_single(' ');
        write_single(h);
        write<true>(t...);
    }
    template <class... T> void writeln(const T&... t) {
        write(t...);
        write_single('\n');
    }

    Printer(FILE* _fp) : fp(_fp) {}
    ~Printer() { flush(); }

  private:
    static constexpr size_t SIZE = 1 << 15;
    FILE* fp;
    char line[SIZE], small[50];
    size_t pos = 0;
    void flush() {
        fwrite(line, 1, pos, fp);
        pos = 0;
    }
    void write_single(const char& val) {
        if (pos == SIZE) flush();
        line[pos++] = val;
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    void write_single(T val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val;  // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char('0' + (val % 10));
            val /= 10;
        }
        for (size_t i = 0; i < len; i++) {
            line[pos + i] = small[len - 1 - i];
        }
        pos += len;
    }
    void write_single(const string& s) {
        for (char c : s) write_single(c);
    }
    void write_single(const char* s) {
        size_t len = strlen(s);
        for (size_t i = 0; i < len; i++) write_single(s[i]);
    }
    template <class T> void write_single(const vector<T>& val) {
        auto n = val.size();
        for (size_t i = 0; i < n; i++) {
            if (i) write_single(' ');
            write_single(val[i]);
        }
    }
    void write_single(long double d){
		{
			long long v=d;
			write_single(v);
			d-=v;
		}
		write_single('.');
		for(int _=0;_<8;_++){
			d*=10;
			long long v=d;
			write_single(v);
			d-=v;
		}
    }
};

Scanner sc(stdin);
Printer pr(stdout);


#ifndef LIBRA_DATA_STRUCTURE_AA_TREE_H_
#define LIBRA_DATA_STRUCTURE_AA_TREE_H_

#include <assert.h>

////////////////////////////////////////////////////////////////////////////////
// leaf node: uncut interval
// internal node: concatnation of intervals for l and r (constitutes AA tree)
// T: monoid representing information of an interval.
//   T()  should return the identity.
//   T(S s)  should represent a single element of the array.
//   T::push(T &l, T &r)  should push the lazy update.
//   T::pull(const T &l, const T &r)  should pull two intervals.
//   T::sz  should represent the length of the interval.
//   T::init(SignedInteger sz_)  should initialize an interval.
template <class T> struct AATree {
  using X = decltype(T().sz);
  AATree *l, *r;
  int lev;
  T t;

  // Creates [0, sz).
  AATree(X sz) : l(nullptr), r(nullptr), lev(0), t() {
    t.init(sz);
  }

  inline X sz() {
    return t.sz;
  }
  inline void push() {
    t.push(l->t, r->t);
  }
  inline void pull() {
    t.pull(l->t, r->t);
  }

  static void free(AATree *u) {
    if (!u) return;
    free(u->l);
    free(u->r);
    delete u;
  }

  //   v---u          v---u   //
  //  / \   \   ->   /   / \  //
  // o   o   o      o   o   o //
  static AATree *rotSkew(AATree *u) {
    if (u->l == nullptr || u->lev != u->l->lev) return u;
    AATree *v = u->l;
    u->l = v->r;
    u->pull();
    v->r = u;
    v->pull();
    return v;
  }
  //                      v   //
  //                     / \  //
  //   u---v---o        u   o //
  //  /   /       ->   / \    //
  // o   o            o   o   //
  static AATree *rotSplit(AATree *u) {
    if (u->r == nullptr || u->lev != u->r->lev) return u;
    if (u->r->r == nullptr || u->lev != u->r->r->lev) return u;
    AATree *v = u->r;
    u->r = v->l;
    u->pull();
    v->l = u;
    ++v->lev;
    v->pull();
    return v;
  }

  // Cuts at a.
  static AATree *cut(AATree *u, X a) {
    if (a <= 0 || u->sz() <= a) return u;
    if (!u->lev) {
      u->l = new AATree(a);
      u->r = new AATree(u->sz() - a);
      u->lev = 1;
      u->push();
      return u;
    }
    u->push();
    if (a <= u->l->sz()) {
      u->l = cut(u->l, a);
      u->pull();
      return rotSplit(rotSkew(u));
    } else {
      u->r = cut(u->r, a - u->l->sz());
      u->pull();
      return rotSplit(rotSkew(u));
    }
  }

  // Applies T::f(args...) to [a, b).
  template <class F, class... Args> void ch(X a, X b, F f, Args &&... args) {
    if (b <= 0 || sz() <= a) return;
    if (a <= 0 && sz() <= b) {
      (t.*f)(args...);
      return;
    }
    push();
    l->ch(a, b, f, args...);
    r->ch(a - l->sz(), b - l->sz(), f, args...);
    pull();
  }

  // Calculates the product for [a, b).
  T get(X a, X b) {
    if (b <= 0 || sz() <= a) return T();
    if (a <= 0 && sz() <= b) return t;
    push();
    const T prodL = l->get(a, b);
    const T prodR = r->get(a - l->sz(), b - l->sz());
    T prod;
    prod.pull(prodL, prodR);
    return prod;
  }

  // Calculates T::f(args...) of a monoid type for [a, b).
  //   op(-, -)  should calculate the product.
  //   e()  should return the identity.
  template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
  auto
#else
  decltype((std::declval<T>().*F())())
#endif
  get(int a, int b, Op op, E e, F f, Args &&... args) {
    if (b <= 0 || sz() <= a) return e();
    if (a <= 0 && sz() <= b) return (t.*f)(args...);
    push();
    const auto prodL = l->get(a, b, op, e, f, args...);
    const auto prodR = r->get(a - l->sz(), b - l->sz(), op, e, f, args...);
    return op(prodL, prodR);
  }

  // TODO: findRight, findLeft
};
////////////////////////////////////////////////////////////////////////////////

#endif  // LIBRA_DATA_STRUCTURE_AA_TREE_H_


// range add, range sum
template <class X, class T> struct NodeSum {
  X sz;
  T sum, lz;
  NodeSum() : sz(0), sum(0), lz(0) {}
  void init(T sz_) {
    sz = sz_;
  }
  void push(NodeSum &l, NodeSum &r) {
    // if (lz) {
      // l.add(lz);
      // r.add(lz);
      // lz = 0;
    // }
  }
  void pull(const NodeSum &l, const NodeSum &r) {
    sz = l.sz + r.sz;
    sum = l.sum + r.sum;
  }
  void add(const T &val) {
    sum += sz * val;
    lz += val;
  }
  T getSum() const {
    return sum;
  }
};


using Node = NodeSum<int, unsigned>;
using AA = AATree<Node>;
void Add(AA *u, int a, int b, unsigned val) {
  if (b <= 0 || u->sz() <= a) return;
  if (a <= 0 && u->sz() <= b) { u->t.add(val); return; }
  u->push();
  Add(u->l, a, b, val);
  Add(u->r, a - u->l->sz(), b - u->l->sz(), val);
  u->pull();
}
unsigned Get(AA *u, int a, int b) {
  if (b <= 0 || u->sz() <= a) return 0;
  if (a <= 0 && u->sz() <= b) return u->t.sum;
  u->push();
  return Get(u->l, a, b) + Get(u->r, a - u->l->sz(), b - u->l->sz());
}

int main() {
  int N, M;
  sc.read(N, M);
  
  const int mask = (1 << M) - 1;
  unsigned x = 0;
  auto seg = new AA(1 << M);
  
  for (int i = 1; i <= N; ++i) {
    int P, Q;
    sc.read(P, Q);
    
    int L = (P + x) & mask;
    int R = (Q + x) & mask;
    if (L > R) swap(L, R);
    ++R;
    seg = AA::cut(seg, L);
    seg = AA::cut(seg, R);
    seg->ch(L, R, &Node::add, i);
    // Add(seg, L, R, i);
    x += seg->get(L, R).sum;
    /*
    x += seg->get(L, R, [&](unsigned y, unsigned z) -> unsigned {
      return y + z;
    }, [&]() -> unsigned {
      return 0;
    }, &Node::getSum);
    */
    // x += Get(seg, L, R);
  }
  
  x &= ((1 << 30) - 1);
  pr.writeln(x);
  
#ifdef LOCAL
  // AA::free(seg);
#endif
  return 0;
}