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

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

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,class u>
int lwb(const vc<t>&v,const u&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&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);
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
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,size_t K,class s=t>
s SUM(const array<t,K>&a){
	return accumulate(all(a),s(0));
}

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

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

template<class A>
auto MIN(const A&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);
}

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

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S,class F>
void soin(S&s,F&&f){
	sort(all(s),forward<F>(f));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(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;
}

template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
	a.insert(a.ed,all(b));
}

template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
	(pb(a,forward<Args>(b)),...);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t>
vc<t> operator+(const vc<t>&a,const vc<t>&b){
	vc<t> c(max(si(a),si(b)));
	rep(i,si(a))c[i]+=a[i];
	rep(i,si(b))c[i]+=b[i];
	return c;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}

template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
	return a-=x;
}

template<class t,class u>
void remval(vc<t>&a,const u&v){
	a.erase(remove(all(a),v),a.ed);
}

template<class VS,class u>
void fila(VS&vs,const u&a){
	fill(all(vs),a);
}

template<class t,class u>
int findid(const vc<t>&vs,const u&a){
	auto itr=find(all(vs),a);
	if(itr==vs.ed)return -1;
	else return itr-vs.bg;
}

template<class t>
void rtt(vc<t>&vs,int i){
	rotate(vs.bg,vs.bg+i,vs.ed);
}

bool dbg=false;

//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 という比較関数が定義されていないと破壊

template<class N>
struct linkcut{
	using Node=typename splaytree<N>::Node;
	using np=typename Node::np;
	np x;
	linkcut(const linkcut&)=delete;
	void operator=(const linkcut&)=delete;
	linkcut(int n){x=new Node[n];}
	~linkcut(){delete[] x;}
	
	int lca(int aa,int bb){
		np a=x+aa,b=x+bb;
		a->expose();
		b->expose();
		if(!a->p)return -1;
		
		np d=a;
		while(a->p!=b){
			if(a->pos()==0)
				d=a->p;
			a=a->p;
		}
		if(a==b->l)return d-x;
		else return b-x;
	}
	//child->par
	void link(int a,int b){
		x[a].LClink(x+b);
	}
	void cutpar(int a){
		x[a].LCcutpar();
	}
	void expose(int a){
		x[a].expose();
	}
	void evert(int a){
		x[a].evert();
	}
	void cutchild(int a){
		x[a].LCcutchild();
	}
	void expose_path(int a,int b){
		x[a].evert();
		x[b].LCcutchild();
	}
	N&operator[](int i){
		return x[i].x;
	}
};

struct N{
	int val,sum;
	N(int v=0):val(v),sum(v){}
	void reverse(){}
	void pushl(N&){}
	void pushr(N&){}
	void clear(){}
	void add(int v){
		val+=v;
		sum+=v;
	}
	void single(){
		sum=val;
	}
	void updatel(const N&x){
		sum+=x.sum;
	}
	void updater(const N&x){
		sum+=x.sum;
	}
};

void slv(){
	int n,k;cin>>n>>k;
	vi a=readvi(n);
	
	linkcut<N> lc(2*(n+1));
	rep(i,n+1){
		lc.link(i,i+n+1);
	}
	rep(i,n){
		lc.link(i+n+1,i+1+n+1);
	}
	
	set<int> avail;
	rep(i,n+1)avail.insert(i);
	vi ans;
	rep(i,n){
		for(auto itr=avail.lower_bound(a[i]-k);
			itr!=avail.ed&&*itr<a[i];
			itr=avail.erase(itr)){
			
			int v=*itr;
			lc.cutpar(v);
			lc.expose(v);
			lc[v].add(1);
			int to=min(v+k,n);
			lc.link(v,to);
		}
		{
			int v=n+1+a[i]-1;
			lc.cutpar(v);
			lc.expose(v);
			lc[v].add(1);
			lc.link(v,a[i]);
		}
		
		lc.expose(0);
		ans.pb(lc[0].sum);
	}
	print(ans);
}

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