#define NDEBUG
#include <bits/stdc++.h>

constexpr int $n = 500000;

namespace Treap {
	void debug(int);
	
	std::mt19937 rng(/*(std::random_device())()*/114515);
	
	struct TreapNode {
		uint32_t lc, rc;
		uint32_t l, r;
		uint32_t tree_l, tree_r;
		uint64_t val, sum, tag;
		uint32_t w, siz;
	} node[$n * 2 + 5];
	
#define int uint64_t
	
	inline TreapNode& $(size_t i) { return node[i]; }
	int O = 1;
	
	int newnode(int l, int r) {
		int res = O++;
		$(res).lc  = $(res).rc = 0;
		$(res).l   = $(res).tree_l = l;
		$(res).r   = $(res).tree_r = r;
		$(res).val = $(res).sum = $(res).tag = 0;
		$(res).w   = rng();
		$(res).siz = 1;
		return res;
	}
	
	void pushup(int i) {
		$(i).sum = $(i).val * uint64_t($(i).r - $(i).l + 1) + $($(i).lc).sum + $($(i).rc).sum;
		$(i).siz = 1 + $($(i).lc).siz + $($(i).rc).siz;
		if($(i).lc) $(i).tree_l = $($(i).lc).tree_l; else $(i).tree_l = $(i).l;
		if($(i).rc) $(i).tree_r = $($(i).rc).tree_r; else $(i).tree_r = $(i).r;
		
		return ;
	}
	
	void pushdown(int i) {
		if($(i).tag) {
			if($(i).lc) {
				TreapNode &lc = $($(i).lc);
				lc.val += $(i).tag;
				lc.tag += $(i).tag;
				lc.sum += $(i).tag * (lc.tree_r - lc.tree_l + 1);	
			}
			if($(i).rc) {
				TreapNode &rc = $($(i).rc);
				rc.val += $(i).tag;
				rc.tag += $(i).tag;
				rc.sum += $(i).tag * (rc.tree_r - rc.tree_l + 1);
			} 
			$(i).tag = 0;
		}
	}
	
	int merge(int l, int r) {
		if(!l) return r; if(!r) return l;
		pushdown(l), pushdown(r);
		if($(l).w > $(r).w) {
			$(l).rc = merge($(l).rc, r);
			pushup(l); return l;
		} else {
			$(r).lc = merge(l, $(r).lc);
			pushup(r); return r;
		}
	}
	
	int merge(int l, int m, int r) {
		return merge(merge(l, m), r);
	}
	
	std::pair<int, int> split_range(int nd, int d) {
		if(!nd) return {0, 0};
		if(d >= $(nd).r) return {nd, 0};
		if(d <  $(nd).l) return {0, nd};
		assert($(nd).l <= d && $(nd).r > d);
		assert($(nd).siz == 1);
		assert($(nd).lc == 0 && $(nd).rc == 0);
		assert($(nd).tree_l == $(nd).l && $(nd).tree_r == $(nd).r);
		int nn = newnode(d + 1, $(nd).r);
		$(nn).val = $(nd).val;
		pushup(nn);
		$(nd).r = d;
		pushup(nd);
		return {nd, nn};
	}
	
	std::pair<int, int> split_by(int nd, std::function<bool(int)> is_left) {
		// std::cerr << "nd = " << nd << char(10);
		if(!nd) return {0, 0};
		pushdown(nd);
		if(is_left(nd)) {
			auto [m, r] = split_by($(nd).rc, is_left);
			$(nd).rc = m; pushup(nd);
			return {nd, r};
		} else {
			auto [l, m] = split_by($(nd).lc, is_left);
			$(nd).lc = m; pushup(nd);
			return {l, nd};
		}
	}
	
	std::pair<int, int> split_by_rank(int nd, int rk) {
		return split_by(nd, [&rk] (int nd) {
			if($($(nd).lc).siz + 1 <= rk) {
				rk -= $($(nd).lc).siz + 1;
				return true;
			} else return false;
		});
	}
	
	std::tuple<int, int, int> fetch_range(int nd, int lb, int rb) {
//		std::cerr << "lb, rb = " << lb << ", " << rb << char(10);
		auto [L, MR] = split_by(nd, [lb] (int nd) {
			return $(nd).r < lb;
		});
		auto [M, R] = split_by(MR, [rb] (int nd) {
			return $(nd).l <= rb;
		});
		
//		debug(L);
//		debug(M);
//		debug(R);
		
		auto [lm, t1] = split_by_rank(M, 1);
		auto [l, t2] = split_range(lm, lb - 1);
//		std::cerr << "[debug] l = " << l << char(10);
		int M2 = merge(t2, t1);
		auto [t3, mr] = split_by_rank(M2, $(M2).siz - 1);
		auto [t4, r] = split_range(mr, rb);
		int M3 = merge(t3, t4);
		
		return {merge(L, l), M3, merge(r, R)};
	}
	
	void debug(int nd) {
		std::cerr << "[debug] ";
		if(nd == 0) std::cerr << "nd = null\n";
		else {
			std::cerr << "nd = " << nd << ":\n";
			std::cerr << "    l = " << $(nd).l << "\n";
			std::cerr << "    r = " << $(nd).r << "\n";
			std::cerr << "    tree_l = " << $(nd).tree_l << "\n";
			std::cerr << "    tree_r = " << $(nd).tree_r << "\n";
		}
		std::cerr << "----------\n";
	}
}

int n, m, p, q;
uint64_t x = 0;

int32_t main(void) {
//	freopen("C2.in", "r", stdin);
	using Treap::$;
	std::cin >> n >> m;
	int root = Treap::newnode(0, (1ull << m) - 1);
	for(uint32_t i = 1; i <= n; ++i) {
		std::cin >> p >> q;
		p = p + x & (1ull << m) - 1;
		q = q + x & (1ull << m) - 1;
		int l = p, r = q;
		if(l > r) std::swap(l, r);		
		auto [L, M, R] = Treap::fetch_range(root, l, r);
//		Treap::debug(L);
//		Treap::debug(M);
//		Treap::debug(R);
//		assert($(M).tree_l == l);
//		assert($(M).tree_r == r);
		$(M).val += i;
		$(M).tag += i;
		$(M).sum += i * uint32_t($(M).tree_r - $(M).tree_l + 1);
		x += $(M).sum;
//		std::cerr << "x = " << x << char(10);
		root = Treap::merge(L, M, R);
		assert($(0).siz == 0);
		assert($(0).val == 0);
		assert($(0).sum == 0);
		assert($(0).tag == 0);
	}
	std::cout << (x & (1 << 30) - 1) << char(10);
	return 0;
}

/*
5 2
2 1
1 3
3 2
1 0
0 2

160 30
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
*/