#include <bits/stdc++.h>

constexpr int $n = 500000;

namespace Treap {
	void debug(int);
	
	std::mt19937 rng(/*(std::random_device())()*/114515);
	
	struct TreapNode {
		int lc, rc;
		int l, r;
		int tree_l, tree_r;
		uint32_t val, sum, tag;
		uint32_t w, siz;
	} node[$n * 2 + 5];
	
	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 * uint32_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;
uint32_t x = 0;

int main(void) {
//	freopen("C2.in", "r", stdin);
	using Treap::$;
	std::cin >> n >> m;
	int root = Treap::newnode(0, (1 << m) - 1);
	for(uint32_t i = 1; i <= n; ++i) {
		std::cin >> p >> q;
		p = p + x & (1 << m) - 1;
		q = q + x & (1 << 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);
	}
	std::cout << (x & (1 << 30) - 1) << char(10);
	return 0;
}