#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

//fast IO by yosupo
//sc.read(string) だと append される
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;
        ref.clear();
        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);

using ll=long long;
//#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t>
bool bis(const vc<t>&v,const t&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
t MIN(const vc<t>&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class t,class u>
pair<t,u> operator+(const pair<t,u>&a,const pair<t,u>&b){
	return mp(a.a+b.a,a.b+b.b);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
S getrev(S s){
	reverse(all(s));
	return s;
}

pi operator+(pi a,pi b){return pi(a.a+b.a,a.b+b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

//copy-constructor，使えません
//find は lazy と組み合わせても動く (Petrozavodsk 2020w Day9 C)
//reverse は未知数
//erase,insert は動く
//split_cmp も動く
//max_right も動く

//AOJ DSL2G
template<class N>
struct splaytree{
	struct Node{
		using np=Node*;
		np l,r,p;
		bool rev;
		N x;
		Node():l(0),r(0),p(0),rev(false),x(){}
		void clear(){
			l=0;
			r=0;
			p=0;
			rev=0;
		}
		void reverse(){
			rev^=true;
			swap(l,r);
			x.reverse();
		}
		void push(){
			if(rev){
				if(l)l->reverse();
				if(r)r->reverse();
				rev=false;
			}
			if(l)x.pushl(l->x);
			if(r)x.pushr(r->x);
			x.clear();
		}
		np update(){
			x.single();
			if(l)x.updatel(l->x);
			if(r)x.updater(r->x);
			return this;
		}
		int pos(){
			if(p&&p->l==this)return -1;
			if(p&&p->r==this)return 1;
			return 0;
		}
		void prepare(){
			if(pos())
				p->prepare();
			push();
		}
		void rotate(){
			np q=p,c;
			if(pos()==1){
				c=l;
				l=p;
				p->r=c;
			}else{
				c=r;
				r=p;
				p->l=c;
			}
			if(c)c->p=p;
			p=p->p;
			q->p=this;
			if(p&&p->l==q)p->l=this;
			if(p&&p->r==q)p->r=this;
			q->update();
		}
		np splay(){
			prepare();
			while(pos()){
				int a=pos(),b=p->pos();
				if(b&&a==b)p->rotate();
				if(b&&a!=b)rotate();
				rotate();
			}
			return update();
		}
		/* deprecated
		template<class F,class...Args>
		np find(F f,Args&&...args){
			if(!(x.*f)(forward<Args>(args)...))return 0;
			push();
			x.single();
			np a=0;
			if(l)a=l->find(f,forward<Args>(args)...);
			if(a)return a;
			if((x.*f)(forward<Args>(args)...))return splay();
			return r->find(f,forward<Args>(args)...);
		}*/
		np left(){
			if(l)return l->left();
			else return splay();
		}
		np right(){
			if(r)return r->right();
			else return splay();
		}
		/*np root(){
			if(p)return p->root();
			else return this;
		}*/
		void chpar(np c){
			if(c){
				assert(!(c->p));
				c->p=this;
			}
		}
		np linkl(np c){
			assert(!l);
			chpar(l=c);
			return update();
		}
		np linkr(np c){
			assert(!r);
			chpar(r=c);
			return update();
		}
		np linklr(np c,np d){
			assert(!l&&!r);
			chpar(l=c);
			chpar(r=d);
			return update();
		}
		np cutl(){
			if(l){
				l->p=0;
				l=0;
			}
			return update();
		}
		np cutr(){
			if(r){
				r->p=0;
				r=0;
			}
			return update();
		}
		//XIX Opencup GP of Zhejiang A
		np get_next(){
			splay();
			if(!r)return 0;
			else return r->left();
		}
		//linkcut 用
		void expose(){
			for(np a=this;a;a=a->p)a->splay();
			for(np a=this;a->p;a=a->p){
				a->p->r=a;
				a->p->update();
			}
			splay();
		}
		void evert(){
			expose();
			if(l){
				l->reverse();
				l=0;
				update();
			}
		}
		void LClink(np a){
			evert();
			p=a;
		}
		void LCcutchild(){
			expose();
			r=0;
			update();
		}
		void LCcutpar() {
			expose();
			assert(l);
			l->p=0;
			l=0;
			update();
		}
	};
	using np=Node*;
	np head;
	int alloc_total=0;
	splaytree(const splaytree&)=delete;
	void operator=(const splaytree&)=delete;
	splaytree():head(0){}
	~splaytree(){
		int del_total=0;
		while(head){
			del_total++;
			np nx=head->p;
			delete head;
			head=nx;
		}
		assert(alloc_total==del_total);
	}
	//TL,MLが厳しいとき
	//FHC2022 Final E
	//もともと 118 秒くらいのコードが 98 秒になったが…
	/*splaytree(){
		const int S=20000000;
		np buf=new Node[S];
		buf[0].p=0;
		rng(i,1,S)buf[i].p=buf+(i-1);
		head=buf+(S-1);
	}
	~splaytree(){}*/
	np allocnode(){
		if(head){
			np res=head;
			head=res->p;
			return res;
		}else{
			alloc_total++;
			return new Node();
		}
	}
	//読んだ直後，x->p 以外の情報は生きている
	void freenode(np x){
		x->p=head;
		head=x;
	}
	/*vc<np> ps;
	unique_ptr<Node[]> buf;
	splaytree(int n):buf(new Node[n]),ps(n){
		rep(i,n)ps[i]=buf.get()+i;
	}
	//alloc/free 系書いてないわ
	*/
	//FHC2022 Final E/range_set/rect_set
	//assume no duplicate free
	void freetree(np x){
		if(!x)return;
		freetree(x->l);
		freetree(x->r);
		freenode(x);
		//ps.pb(x);
	}
	template<class...Args>
	np nn(Args&&...args){
		np a=allocnode();
		a->l=0;
		a->r=0;
		a->p=0;
		a->x=N(forward<Args>(args)...);
		return a;
	}
	np merge(np a,np b){
		if(!a)return b;
		if(!b)return a;
		return b->splay()->left()->linkl(a->splay());
	}
	//GCJ2022 Round2 D
	template<class...Args>
	np merge(np a,np b,Args...args){
		return merge(merge(a,b),args...);
	}
	template<bool C,class F,class...Args>
	pair<np,np> max_right_sub(np a,F f,Args&&...args){
		N cur;
		np x=0,y=0;
		while(a){
			a->push();
			N nx=a->x;nx.single();
			if(a->l)nx.updatel(a->l->x);
			nx.updatel(cur);
			if((nx.*f)(forward<Args>(args)...)){
				cur=nx;
				x=a;
				a=a->r;
			}else{
				y=a;
				a=a->l;
			}
		}
		if(x){
			x->splay();
			if constexpr(C)x->cutr();
		}
		if(y)y->splay();
		return mp(x,y);
	}
	//max_right で失敗する最初のノードを根にする
	//そのようなものがない場合は false が返ってくる
	template<class F,class...Args>
	bool max_right_splay(np&a,F f,Args&&...args){
		auto [x,y]=max_right_sub<false>(a,f,forward<Args>(args)...);
		if(y){
			a=y;
			return true;
		}else{
			a=x;
			return false;
		}
	}
	//分けた列の右端と左端が返ってくる
	//CF Dytechlab Cup 2022 G (lazy あり)
	template<class F,class...Args>
	pair<np,np> max_right_split(np a,F f,Args&&...args){
		return max_right_sub<true>(a,f,forward<Args>(args)...);
	}
	//XX Opencup GP of Wroclaw D
	//分けた列の右端と左端が返ってくる
	//CF740 D (lazy あり)
	//CF Dytechlab Cup 2022 G (lazy あり)
	template<bool C,class F,class T>
	static pair<np,np> split_sub(np a,F cmp,T v){
		np x=0,y=0;
		while(a){
			a->push();
			if(cmp(a->x,v)){
				x=a;
				a=a->r;
			}else{
				y=a;
				a=a->l;
			}
		}
		if(x){
			x->splay();
			if constexpr(C)x->cutr();
		}
		if(y)y->splay();
		return mp(x,y);
	}
	template<class F,class T>
	pair<np,np> split_cmp(np a,F cmp,T v){
		return split_sub<true>(a,cmp,v);
	}
	//cmp(x,v)=false になる最初の x を根にして返す
	//そのようなものがない場合は false が返ってくる
	//FHC2022 Final E/range_set/rect_set
	template<class F,class T>
	bool lower_bound_cmp(np&a,F cmp,T v){
		auto [x,y]=split_sub<false>(a,cmp,v);
		if(y){
			a=y;
			return true;
		}else{
			//not verified?
			a=x;
			return false;
		}
	}
	//XIX Opencup GP of Zhejiang A
	//FHC2022 Final E/range_set/rect_set
	template<class F>
	void insert_cmp(np&x,F cmp,np v){
		assert(!v->l&&!v->r&&!v->p&&!v->rev);
		//auto [a,b]=split_cmp(x,f,v->x);
		//x=v->linklr(a,b);
		if(!x){
			x=v;
			return;
		}else{
			np p=0;
			bool l;
			while(x){
				x->push();
				p=x;
				if(cmp(x->x,v->x)){
					l=false;
					x=x->r;
				}else{
					l=true;
					x=x->l;
				}
			}
			if(l){
				p->linkl(v);
			}else{
				p->linkr(v);
			}
			x=v->splay();
		}
	}
	//XX Opencup GP of Wroclaw D
	//FHC2022 Final E/range_set/rect_set
	template<class F,class...Args>
	void emplace_cmp(np&x,F f,Args&&...args){
		insert_cmp(x,f,nn(forward<Args>(args)...));
	}
	//FHC2022 Final E/range_set/rect_set
	template<class...Args>
	void emplace(np&x,Args&&...args){
		emplace_cmp(x,less<N>(),forward<Args>(args)...);
	}
	//XX Opencup GP of Wroclaw D
	pair<np,np> erase_sub(np x){
		x->splay();
		if(x->l)x->l->p=0;
		if(x->r)x->r->p=0;
		freenode(x);
		return mp(x->l,x->r);
	}
	//CF Dytechlab Cup 2022 G
	void erase(np&x){
		auto [a,b]=erase_sub(x);
		x=merge(a,b);
	}
	//FHC2022 Final E/range_set/rect_set
	//less,eq,
	template<class F,class T,class G>
	bool erase_cmp_eq(np&x,F f,G g,T v){
		if(lower_bound_cmp(x,f,v)&&g(x->x,v)){
			erase(x);
			return true;
		}
		return false;
	}
	//FHC2022 Final E/range_set/rect_set
	template<class T>
	bool erase(np&x,T v){
		return erase_cmp_eq(x,less<N>(),equal_to<N>(),v);
	}
	//Petrozavodsk 2020w Day9 H
	np isolate(np x){
		x->splay();
		if(x->l)x->l->p=0;
		if(x->r)x->r->p=0;
		np res=merge(x->l,x->r);
		x->x.single();
		x->clear();
		return res;
	}
	template<class t>
	np build(vc<t> v){
		vc<np> cur;
		for(auto z:v)cur.pb(nn(z));
		while(cur.size()>1){
			int s=cur.size();
			vc<np> nx((s+1)/2);
			for(int i=0;i<s;i+=2){
				if(i+1<s)nx[i/2]=merge(cur[i],cur[i+1]);
				else nx[i/2]=cur[i];
			}
			swap(nx,cur);
		}
		return cur[0];
	}
	/*
	//NOT VERIFIED
	//lower_bound したものを根に移して node を返す．
	//lower_bound の結果が end だと空が返ってくるらしい
	//USACO2021 USOPEN Platinum A
	template<class F>
	np lower_bound_cmp(np a,F cmp,N v){
		auto [x,y]=split_cmp(a,cmp,v);
		np res=nullptr;
		if(y)res=y->left();
		merge(x,res);
		if(res)res->splay();
		return res;
	}
	*/
	//XIX Opencup GP of Zhejiang A
	//a-b なる部分を取り出し，x,y(a-b),z を返す
	//a と b が異なる木に属する，また，a と b の順序がおかしい場合，何が起きるかは不明
	tuple<np,np,np> split_range(np a,np b){
		{//debug
			a->splay();
			b->splay();
			int lastpos;
			auto c=a;
			while(c&&c!=b){
				lastpos=c->pos();
				c=c->p;
			}
			assert(c==b);
			assert(lastpos==-1);
		}
		a->splay();
		np x=a->l;
		a->cutl();
		b->splay();
		np z=b->r;
		b->cutr();
		return mt(x,b,z);
	}
	//CF743F(TLE)
	//The 2022 ICPC Asia Nanjing Regional Contest H
	template<class F>
	void weighted_merge_rec_cmp(np&tar,F f,np x){
		if(!x)return;
		x->push();
		np l=x->l,r=x->r;
		x->x.single();
		x->clear();
		weighted_merge_rec_cmp(tar,f,l);
		insert_cmp(tar,f,x);
		weighted_merge_rec_cmp(tar,f,r);
	}
	template<class F>
	np weighted_merge_cmp(np a,F f,np b){
		if(!a)return b;
		if(!b)return a;
		if(a->x.len<b->x.len)swap(a,b);
		weighted_merge_rec_cmp(a,f,b);
		return a;
	}
	//Petrozavodsk 2020w Day9 C
	void enumerate(np x,vc<N>&dst){
		if(!x)return;
		x->push();
		enumerate(x->l,dst);
		dst.pb(x->x);
		enumerate(x->r,dst);
	}
	/* deprecated
	//Petrozavodsk 2020w Day9 H
	template<class F>
	np insert(np r,np x,F f){
		np a,b;tie(a,b)=split(r,f,x->x);
		return merge(merge(a,x),b);
	}
	template<class F,class...Args>
	np insert(np r,F f,Args&&...args){
		np x=nn(forward<Args>(args)...);
		np a,b;tie(a,b)=split(r,f,x->x);
		return merge(merge(a,x),b);
	}
	//左の列の根は右端とは限らない！
	//右の列の根は左端だと思う
	template<class F,class...Args>
	pair<np,np> split(np a,F f,Args&&...args){
		if(!a)return {0,0};
		np b=a->find(f,forward<Args>(args)...);
		if(b){
			np c=b->l;
			return {c,b->cutl()};
		}
		return {a,0};
	}
	//GCJ2022 Round2 D
	tuple<np> split_by_len(np a){
		return a;
	}
	template<class...Args>
	auto split_by_len(np a,int len,Args...args){
		assert((!a&&len==0)||inc(0,len,a->x.len));
		auto [b,c]=split(a,&N::find_by_len,len);
		assert(len==0);
		return tuple_cat(tuple{b},split_by_len(c,args...));
	}
	//Petrozavodsk 2020w Day9 C
	template<class F>
	np weighted_merge_rec(np x,np tar,F f){
		if(!x)return tar;
		x->push();
		tar=weighted_merge_rec(x->l,tar,f);
		tar=weighted_merge_rec(x->r,tar,f);
		x->x.single();
		x->clear();
		return insert(tar,x,f);
	}
	//Petrozavodsk 2020w Day9 C
	template<class F>
	np weighted_merge(np a,np b,F f){
		if(!a)return b;
		if(!b)return a;
		if(a->x.sz<b->x.sz)swap(a,b);
		return weighted_merge_rec(b,a,f);
	}
	*/
};
//デフォルトコンストラクターが null node になっているべき (例えば len=0)
//N::reverse
//N::push→ pushl,pushr
//副作用なし,１個の子にpush
//N::clear
//lazy tagを消去
//N::single
//ノード単体の情報を元に部分木情報を初期化
//N::updatel,updater
//N::find
//find はその部分木内に目標とするノードがあるかどうかを返す
//split のやり方を変えたい
//max_right のノリで split をする
//split_cmp は cmp(x,v) が true になる最大の x を見つけてそれで分離
//↓deprecared
//split は find で見つけたものが右の部分木の left になるように分離する
//普通に a<b を渡すと lower_bound と同じ効果が得られる
//split_by_len で左 len 個とそれ以外に分離する
//find_by_len という比較関数が定義されていないと破壊

//multiset<int> で値の sum が取れるだけ
template<int K>
struct N{
	using A=array<uint,K>;
	int key;
	A val,sum;
	N(){}
	N(int k,A v):key(k),val(v){single();}
	void reverse(){}
	void pushl(N&){
	}
	void pushr(N&){
	}
	void clear(){
	}
	void single(){
		sum=val;
	}
	void update(const N&x){
		rep(i,K)sum[i]+=x.sum[i];
	}
	void updatel(const N&x){update(x);}
	void updater(const N&x){update(x);}
	bool operator<(const N&r)const{
		return key<r.key;
	}
	uint eval(ull x){
		return sum[0]+sum[1]*x;
	}
};

void slv(){
	int n,m;sc.read(n,m);
	//2^30
	splaytree<N<2>> t;
	using np=decltype(t)::np;
	np root=nullptr;
	uint ans=0;
	rng(i,1,n+1){
		uint p,q;sc.read(p,q);
		p=(p+ans)&mask(m);
		q=(q+ans)&mask(m);
		uint l,r;tie(l,r)=minmax(p,q);
		r++;
		dmp2(l,r);
		uint sum=uint(i)*(r-l);
		{
			auto [x,y]=t.split_cmp(root,less<N<2>>(),N<2>(l,{}));
			if(x)sum-=x->x.eval(l);
			root=t.merge(x,y);
		}
		{
			auto [x,y]=t.split_cmp(root,less<N<2>>(),N<2>(r,{}));
			if(x)sum+=x->x.eval(r);
			root=t.merge(x,y);
		}
		ans+=sum;
		t.emplace(root,l,N<2>::A{-(uint)i*l,(uint)i});
		t.emplace(root,r,N<2>::A{(uint)i*r,-(uint)i});
	}
	pr.writeln(ans&mask(30));
	t.freetree(root);
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	//int t;cin>>t;rep(_,t)
	slv();
}