#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

bool dbg=false;

#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));
}

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);
}
string rand_string(int n,char lw,char up){
	string s(n,'?');
	rep(i,n)s[i]=rand_int(lw,up);
	return s;
}

int current_run_id,run_batch_size=1000;
int calc_random_limit(){
	return current_run_id/run_batch_size+1;
}
#ifndef int
void generate_single(int&a){
	a=rand_int(1,calc_random_limit());
}
#endif
void generate_single(ll&a){
	a=rand_int(1,calc_random_limit());
}
void generate_single(string&a){
	int n;generate_single(n);
	a=rand_string(n,'a','b');
}
//https://trap.jp/post/1224/
template<class... Args>
void input(Args&... a){
	if(dbg){
		(generate_single(a),...);
	}else{
		(cin >> ... >> a);
	}
}
#define INT(...) int __VA_ARGS__;input(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;input(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;input(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;input(__VA_ARGS__)
#define overload3(a,b,c,d,...) d
#define VI2(name,size) vi name(size);rep(i,size)input(name[i]);
#define VI3(name,size,offset) vi name(size);rep(i,size)input(name[i]),name[i]+=offset;
#define VI(...) overload3(__VA_ARGS__,VI3,VI2)(__VA_ARGS__)

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){
		if(dbg)cout<<endl;
		else 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 S> void mkuni(S&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

template<class t> bool isuni(vc<t> v){
	int s=si(v);
	mkuni(v);
	return si(v)==s;
}

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

template<class S,class u>
int lwb(const S&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,class u>
pair<t,u> operator-(pair<t,u> a){return mp(-a.a,-a.b);}
template<class t,class u>
istream&operator>>(istream&is,pair<t,u>&a){
	return is>>a.a>>a.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);
}
//消した要素の個数を返してくれる
//UCUP 2-8-F
template<class t,class F>
int remif(vc<t>&a,F f){
	auto itr=remove_if(all(a),f);
	int res=a.ed-itr;
	a.erase(itr,a.ed);
	return res;
}

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);
}

//Multiuni2023-8 C
//f(lw)=false,...,f(n-1)=false,f(n)=true,...,f(up)=true,
//のときに n を返す
template<class F>
int find_min_true(int lw,int up,F f){
	while(up-lw>1){
		const int mid=(lw+up)/2;
		if(f(mid))up=mid;
		else lw=mid;
	}
	return up;
}
//f(lw)=true,f(up)=false
template<class F>
int find_max_true(int lw,int up,F f){
	while(up-lw>1){
		const int mid=(lw+up)/2;
		if(f(mid))lw=mid;
		else up=mid;
	}
	return lw;
}

//N() が単位元
//VERIFY: yosupo
//CF407E
template<class N>
struct segtree{
	vc<N> x;
	int n,s;
	segtree(){}
	template<class t>
	segtree(const vc<t>&a){
		n=a.size();
		s=1;
		while(s<n){s*=2;}
		x.resize(s*2);
		rep(i,n)
			x[s+i]=N(a[i]);
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	//NOT Verified
	segtree(int nn){
		resize(nn);
	}
	void resize(int nn){
		n=nn;
		s=1;
		while(s<n){s*=2;}
		x.assign(s*2,N());
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	template<class t>
	void load(const vc<t>&a){
		n=a.size();
		s=1;
		while(s<n){s*=2;}
		x.resize(s*2);
		rep(i,n)
			x[s+i]=N(a[i]);
		rng(i,n,s)
			x[s+i]=N();
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void clear(){
		rep(i,n)
			x[s+i]=N();
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	N point_get(int i){
		assert(inc(0,i,n-1));
		return x[i+s];
	}
	void point_set(int i,const N&t){
		assert(inc(0,i,n-1));
		i+=s;
		x[i]=t;
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void point_merge(int i,const N&t){
		assert(inc(0,i,n-1));
		i+=s;
		x[i]=N::merge(x[i],t);
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	template<class F,class...Args>
	void point_change(int i,F f,Args&&...args){
		assert(inc(0,i,n-1));
		i+=s;
		(x[i].*f)(forward<Args>(args)...);
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	N composite(int b,int e){
		assert(0<=b&&b<=e&&e<=n);
		N lf,rt;
		for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){
			if (l&1){
				lf=N::merge(lf,x[l]);
				l++;
			}
			if (r&1){
				r--;
				rt=N::merge(x[r],rt);
			}
		}
		return N::merge(lf,rt);
	}
	N getall(){
		return x[1];
	}
	//UTPC2020E
	//n 超えるかもしれない
	template <class F,class... Args> 
	pair<int,N> max_right(int l,F f,Args&&... args){
		assert((N().*f)(forward<Args>(args)...));
		assert(0<=l&&l<=n);
		if(l==n)return mp(n,N());
		l+=s;
		
		N sm;
		assert((sm.*f)(forward<Args>(args)...));
		do {
			while (l % 2 == 0) l >>= 1;
			if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){
				while (l < s) {
					l = (2 * l);
					N tmp=N::merge(sm,x[l]);
					if ((tmp.*f)(forward<Args>(args)...)) {
						sm = tmp;
						l++;
					}
				}
				return mp(l - s,sm);
			}
			sm = N::merge(sm, x[l]);
			l++;
		} while ((l & -l) != l);
		return mp(n,sm);
	}
	//UCUP-2-22-K
	template <class F,class... Args> 
	pair<int,N> min_left_withinit(int r,N sm,F f,Args&&... args){
		assert((sm.*f)(forward<Args>(args)...));
		assert(0<=r&&r<=n);
        if(r==0)return mp(0,sm);
        r+=s;
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {
                while (r < s) {
                    r = (2 * r + 1);
                    N tmp=N::merge(x[r],sm);
                    if ((tmp.*f)(forward<Args>(args)...)) {
                        sm = tmp;
                        r--;
                    }
                }
                return mp(r + 1 - s,sm);
            }
            sm = N::merge(x[r], sm);
        } while ((r & -r) != r);
        return mp(0,sm);
    }
	//UTPC2020E
	template <class F,class... Args> 
	pair<int,N> min_left(int r,F f,Args&&... args){
		return min_left_withinit(r,N(),f,forward<Args>(args)...);
    }
    //行列とか乗せて必要なのはベクトルとの積，みたいなときに使える？
    //CF Goodbye 2016 E
    //CF 896 F
	template<class F,class T,class... Args>
	T accumulate(int l,int r,F f,T t,Args&&... args) {
		assert(0<=l&&l<=r&&r<=n);
		static int buf[2][30];
		int cnt[2]{};
		for(l+=s,r+=s;l<r;l>>=1,r>>=1){
			if(l&1)buf[0][cnt[0]++]=l;
			if(r&1)buf[1][cnt[1]++]=r-1;
			l++;
		}
		rep(i,cnt[0])t=(x[buf[0][i]].*f)(t,forward<Args>(args)...);
		per(i,cnt[1])t=(x[buf[1][i]].*f)(t,forward<Args>(args)...);
		return t;
	}
};

//内部でグラフをいじるから in,out を使うときは注意
//hei[v] -> heavy edge で潜っていった時，自分含めて何個あるか
//pe[v]: v->par[v] の辺の情報
//-有向木のときは上から下の辺を入れてる
//-無向木のときは下から上の辺を入れてる
//VERIFY: yosupo
//CF530F
//CodeChef Persistent Oak
//AOJ GRL5C
template<class E>
struct HLD{
	vvc<E> g;
	int n,rt,cnt;
	vi sub,in,out,par,head,dep,hei,ni;
	vc<E> pe;
	int dfs1(int v,int p,int d){
		par[v]=p;
		dep[v]=d;
		for(auto itr=g[v].bg;itr!=g[v].ed;itr++)
			if(*itr==p){
				pe[v]=*itr;
				g[v].erase(itr);
				break;
			}
		for(auto&e:g[v]){
			pe[e]=e;
			sub[v]+=dfs1(e,v,d+1);
			if(sub[g[v][0]]<sub[e])
				swap(g[v][0],e);
		}
		return sub[v];
	}
	void dfs2(int v,int h){
		in[v]=cnt++;
		head[v]=h;
		for(int to:g[v])
			dfs2(to,to==g[v][0]?h:to);
		out[v]=cnt;
		if(si(g[v]))hei[v]=hei[g[v][0]]+1;
	}
	HLD(){}
	HLD(const vvc<E>&gg,int rr):g(gg),n(g.size()),rt(rr),cnt(0),
		sub(n,1),in(n),out(n),par(n,-1),head(n),dep(n),hei(n,1),ni(n),
		pe(n){
		dfs1(rt,-1,0);
		dfs2(rt,rt);
		rep(i,n)ni[in[i]]=i;
	}
	int lca(int a,int b){
		while(head[a]!=head[b]){
			if(dep[head[a]]>dep[head[b]])
				swap(a,b);
			b=par[head[b]];
		}
		if(dep[a]>dep[b])
			swap(a,b);
		return a;
	}
	int len(int a,int b){
		return dep[a]+dep[b]-dep[lca(a,b)]*2;
	}
	bool asde(int a,int b){
		return in[a]<=in[b]&&out[b]<=out[a];
	}
	//UCUP 1-22 F
	int adv(int a,int d){
		if(hei[a]<=d)return -1;
		else return ni[in[a]+d];
	}
	//CF692F
	int getpar(int v,int len){
		assert(dep[v]>=len);
		int tar=dep[v]-len;
		while(1){
			int h=head[v];
			if(dep[h]<=tar){
				return ni[in[h]+(tar-dep[h])];
			}
			v=par[h];
		}
		assert(false);
	}
	//1st UCUP 13 G
	int jump(int a,int b,int d){
		int c=lca(a,b);
		if(d<=(dep[a]-dep[c])){
			return getpar(a,d);
		}else{
			d=(dep[a]+dep[b]-dep[c]*2)-d;
			assert(d>=0);
			return getpar(b,d);
		}
	}
	//XX Opencup GP of Korea
	//CF625 F
	//2020 Multi-Uni Contest Day5 G
	//CF415E
	//Universal Cup 2023 Stage 1 G
	vi index;
	//vs を含む virtual tree を返す
	//返すのは virtual tree に使われた頂点と，辺の集合
	//辺の端点は，virtual tree における番号
	//元の木における番号を virtual tree の頂点番号に写すのが，index という変数
	//辺は ch->par の順
	//virtual tree は行き掛け順で番号がついている
	//特に，頂点 0 が根になるようにできている
	//pair<vi,vc<pi>> tree_compress(vi vs){
	void tree_compress(vi&vs,vc<pi>&es){
		if(si(index)==0)index.resize(n);
		assert(index.size());
		auto comp = [&](int x,int y){
			return in[x] < in[y];
		};
		sort(all(vs),comp);
		assert(is_sorted(all(vs),comp));
		vs.erase(unique(all(vs)),vs.ed);
		int k = vs.size();
		rep(i,k-1){
			vs.pb(lca(vs[i],vs[i+1]));
		}
		sort(all(vs),comp);
		vs.erase(unique(all(vs)),vs.ed);
		k = vs.size();
		rep(i,k) index[vs[i]] = i;
		es.clear();
		rng(i,1,k){
			int p = lca(vs[i-1],vs[i]);
			es.eb(i,index[p]);
		}
		//return mp(vs,es);
	}
	//assume a is desdendant of b
	//ex=true <=> exclude b
	template<class F>
	void subpath_work(int a,int b,bool ex,F f){
		while(1){
			if(head[a]==head[b]){
				f(in[b]+ex,in[a]+1);
				break;
			}else{
				int h=head[a];
				f(in[h],in[a]+1);
				a=par[h];
			}
		}
	}
	//KUPC2021E
	//パスに対する操作順に注意
	//euler-tour 順にしたときの区間に作用していることに注意
	//ex=true exclude lca(a,b) (=apply path edges)
	template<class F>
	void path_work(int a,int b,bool ex,F f){
		int c=lca(a,b);
		subpath_work(a,c,ex,f);
		subpath_work(b,c,true,f);
	}
	//v->false
	//-1->true
	//root-v パス上で f(x)=true となる最も深い頂点を返す
	//CF857G
	template<class F>
	int find_lowest(int v,F f)const{
		while(v>=0){
			int h=head[v];
			if(!f(h)){
				v=par[h];
			}else{
				int l=0,r=dep[v]-dep[h]+1;
				while(r-l>1){
					const int mid=(l+r)/2;
					if(f(ni[in[h]+mid]))l=mid;
					else r=mid;
				}
				return ni[in[h]+l];
			}
		}
		return -1;
	}
	//-1->false
	//v->true
	//root-v パス上で f(x)=true となる最も浅い頂点を返す
	//Yandex Cup 2023 Semifinal F (TLE...)
	template<class F>
	int find_highest(int v,F f)const{
		while(1){
			int h=head[v];
			int p=par[h];
			if(p!=-1&&f(p)){
				v=p;
			}else{
				int l=-1,r=dep[v]-dep[h];
				while(r-l>1){
					const int mid=(l+r)/2;
					if(f(ni[in[h]+mid]))r=mid;
					else l=mid;
				}
				return ni[in[h]+r];
			}
		}
		assert(false);
	}
};

//永続用のコードを適当にコピーしてきました！
//壊れても知りません！
//UCUP 1-16 C (lazyなし)
//コメントアウトしてあるところは全く試してない
//CF887F (lazy)
//TOKI35G (lazy)
//#define AVLLAZY
//https://qiita.com/QCFium/items/3cf26a6dc2d49ef490d7
template<class N>
struct avl{
	struct N2{
		using np=N2*;
		N v;
		np l,r,p;
		int h;
		//h は葉までの最長パスのノード数
		//null node で 0
		//v has no lazy data
		np upd(){
			v.single();
			h=0;
			if(l){
				l->p=this;
				v.updatel(l->v);
				chmax(h,l->h);
			}
			if(r){
				r->p=this;
				v.updater(r->v);
				chmax(h,r->h);
			}
			h++;
			p=nullptr;
			return this;
		}
		np L(np x){l=x;return upd();}
		np R(np x){r=x;return upd();}
		np LR(np x,np y){l=x;r=y;return upd();}
	};
	using np=N2*;
	const int S;
	unique_ptr<N2[]> buf;
	avl(int ss):S(ss),buf(new N2[S]){}
	int used=0;
	np nn(N v){
		assert(used<S);
		buf[used]=N2{v,0,0,0,1};
		return &buf[used++];
	}
	void emplace_new(np x,N v){
		*x=N2{v,0,0,0,1};
	}
	/*void checkvalidity(){
		rep(i,used){
			np x=&buf[i];
			if(x->p!=(np)-1){
				if(x->p){
					int j=x->p-buf.get();
					dmp2(i,j);
					assert(x->p->p!=np(-1));
					assert(x->p->l==x||x->p->r==x);
				}
			}
		}
	}*/
	//a is not null
	np push(np x){
		#ifdef AVLLAZY
		if(x->l)x->v.pushl(x->l->v);
		if(x->r)x->v.pushr(x->r->v);
		x->v.clear();
		#endif
		return x;
	}
	int hei(np x){return x?x->h:0;}
	N val(np x){return x?x->v:N();}
	int ok(int a,int b){return abs(a-b)<=1;}
	//x is already cloned
	//x needs upd
	//hei(res)==max(hei(x->l),hei(x->r))+(0 or 1)
	//O(|hei(x->r)-hei(x->r)|)
	np balance(np x){
		np a=x->l;
		np b=x->r;
		int dif=hei(a)-hei(b);
		if(inc(-1,dif,1)){
			return x->upd();
		}else if(dif<0){
			push(b);
			if(dif<-2){
				return Lb(b,Rb(x,b->l));
			}else if(ok(hei(b->l)+1,hei(b->r))){
				return b->L(x->R(b->l));
			}else{
				np y=push(b->l);
				return y->LR(x->R(y->l),b->L(y->r));
			}
		}else if(dif>0){
			push(a);
			if(dif>2){
				return Rb(a,Lb(x,a->r));
			}else if(ok(hei(a->l),hei(a->r)+1)){
				return a->R(x->L(a->r));
			}else{
				np y=push(a->r);
				return y->LR(a->R(y->l),x->L(y->r));
			}
		}else assert(false);
	}
	np Lb(np x,np a){x->l=a;return balance(x);}
	np Rb(np x,np a){x->r=a;return balance(x);}
	//hei(res)==max(hei(a),hei(b))+(0 or 1)
	//O(hei(a)+hei(b))
	//a,b は基本的にはちゃんとした木なのだが，p に変な情報が入っているかもしれないので消しておく
	//TOKI35G
	np mergedfs(np a,np b){
		if(a==0&&b==0)return nullptr;
		if(a==0){
			b->p=nullptr;
			return b;
		}
		if(b==0){
			a->p=nullptr;
			return a;
		}
		if(hei(a)<hei(b)){
			push(b);
			return Lb(b,mergedfs(a,b->l));
		}else{
			push(a);
			return Rb(a,mergedfs(a->r,b));
		}
	}
	template<class...Args>
	np merge(Args...args){
		np res=0;
		for(auto x:{args...})res=mergedfs(res,x);
		return res;
	}
	/*template <class F,class... Args> 
	pair<np,np> max_right(np x,N cur,F f,Args&&... args){
		if(x==0)return mp(np(0),np(0));
		push(x);
		x->v.single();
		N nx=cur;
		nx.updater(val(x->l));
		nx.updater(val(x));
		if((nx.*f)(forward<Args>(args)...)){
			auto [a,b]=max_right(x->r,nx,f,forward<Args>(args)...);
			return mp(Rb(x,a),b);
		}else{
			auto [a,b]=max_right(x->l,cur,f,forward<Args>(args)...);
			return mp(a,Lb(x,b));
		}
	}
	template <class F,class... Args> 
	pair<np,np> max_right(np x,F f,Args&&... args){
		return max_right(x,N(),f,forward<Args>(args)...);
	}*/
	//f(v,args)=true が左，false が右
	//not verified
	template <class F,class... Args>
	pair<np,np> split_by_cmp(np x,F f,Args&&... args){
		if(x==0)return mp(np(0),np(0));
		push(x);
		x->v.single();
		if(f(x->v,forward<Args>(args)...)){
			auto [a,b]=split_by_cmp(x->r,f,forward<Args>(args)...);
			return mp(Rb(x,a),b);
		}else{
			auto [a,b]=split_by_cmp(x->l,f,forward<Args>(args)...);
			return mp(a,Lb(x,b));
		}
	}
	//lower_bound の位置に insert
	//FHC 2022 Round3 E2 (without LAZY)
	//CF887F (insert した結果のノードも返す)
	template <class F>
	void insert_cmp(np&x,F f,np v){
		assert(!v->l&&!v->r&&!v->p);
		if(x==0){
			x=v;
			return;
		}
		push(x);
		x->v.single();
		if(f(x->v,v->v))
			insert_cmp(x->r,f,v);
		else
			insert_cmp(x->l,f,v);
		x=balance(x);
	}
	//emplace に書き換えないと
	//insert_cmp ように書き換えないと
	/*template <class F>
	np insert_by_cmp(np&x,F f,const N&v){
		auto [newx,ins]=insertdfs(x,f,v);
		x=newx;
		return ins;
	}*/
	//x のデータをこちょこちょ書き換えたので upd を反映させて root を返す
	//CF887F
	void reload(np x){
		while(x){
			np y=x->p;
			x->upd();
			x=y;
		}
	}
	static np vs[];
	//x から親までの path を vs に保存
	//ついでに push もしておく
	//CF887F
	int prep(np x){
		int s=0;
		vs[s++]=x;
		while(vs[s-1]->p){
			vs[s]=vs[s-1]->p;
			s++;
		}
		per(i,s)push(vs[i]);
		return s;
	}
	//CF887F
	//TOKI35G erase した直後に x->v を見ると正しいデータが入っている
	np erase(np x){
		int s=prep(x);
		//delete x
		x->p=(np)-1;// (p から delete 済みかどうかをチェックできるようにする)
		np cur=mergedfs(x->l,x->r);
		rng(i,1,s){
			if(vs[i]->l==vs[i-1]){
				cur=Lb(vs[i],cur);
			}else{
				cur=Rb(vs[i],cur);
			}
		}
		return cur;
	}
	//x,res は push されていて即使用可能になっている
	//CF887F
	np next(np x){
		int s=prep(x);
		if(x->r){
			np cur=x->r;
			while(cur->l){
				push(cur);
				cur=cur->l;
			}
			push(cur);
			return cur;
		}
		rng(i,1,s)if(vs[i]->l==vs[i-1])return vs[i];
		return nullptr;
	}
	//CF887F
	np prev(np x){
		int s=prep(x);
		if(x->l){
			np cur=x->l;
			while(cur->r){
				push(cur);
				cur=cur->r;
			}
			push(cur);
			return cur;
		}
		rng(i,1,s)if(vs[i]->r==vs[i-1])return vs[i];
		return nullptr;
	}
	//CF887F
	//TOKI35G
	template <class F,class... Args>
	void chroot(np x,F f,Args&&... args){
		if(!x)return;
		assert(x->p==nullptr);
		(x->v.*f)(forward<Args>(args)...);
	}
	/*//lower_bound の位置を erase
	//erase が実際に走ったかどうかが bool で返る
	//FHC 2022 Round3 E2 (without LAZY, all true)
	template <class F>
	pair<bool,np> erasedfs(np x,F f,const N&v){
		if(x==0)return mp(false,np(0));
		push(x);
		x->v.single();
		if(f(x->v,v)){
			auto [done,y]=erasedfs(x->r,f,v);
			return mp(done,Rb(x,y));
		}else{
			auto [done,y]=erasedfs(x->l,f,v);
			if(done)return mp(true,Lb(x,y));
			else return mp(true,merge(y,x->r));
		}
	}
	template <class F>
	pair<bool,np> erase_by_cmp(np x,F f,const N&v){
		return erasedfs(x,f,v);
	}
	//lower_bound が存在するかどうかを bool で返す
	//存在するならノード情報も返す
	//FHC 2022 Round3 E2 (without LAZY)
	template <class F>
	pair<bool,N> lower_bound_by_cmp(np x,F f,N v){
		np res=0;
		while(x){
			push(x);
			x->v.single();
			if(f(x->v,v)){
				x=x->r;
			}else{
				res=x;
				x=x->l;
			}
		}
		if(res)return mp(true,res->v);
		else return mp(false,N());
	}*/
	//TOKI35G
	pair<np,np> split(np x,const N&v){return split_by_cmp(x,less<N>(),v);}
	//TOKI35G
	//np insert(np&x,const N&v){return insert_by_cmp(x,less<N>(),v);}
	//UCUP 2-24-H
	void insert(np&x,np v){return insert_cmp(x,less<N>(),v);}
	//pair<bool,np> erase(np x,const N&v){return erase_by_cmp(x,less<N>(),v);}
	//pair<bool,N> lower_bound(np x,const N&v){return lower_bound_by_cmp(x,less<N>(),v);}
	/*template<class T>
	np build(const T&rw){
		auto dfs=[&](auto self,int l,int r)->np{
			if(l==r)return 0;
			int m=(l+r)/2;
			np x=nn(rw[m]);
			return x->LR(self(self,l,m),self(self,m+1,r));
		};
		return dfs(dfs,0,si(rw));
	}*/
	//CF887F
	vc<N> listup(np root){
		vc<N> res;
		auto dfs=[&](auto self,np x)->void{
			if(x==0)return;
			push(x);
			self(self,x->l);
			res.pb(x->v);
			self(self,x->r);
		};
		dfs(dfs,root);
		return res;
	}
};
template<class N>typename avl<N>::np avl<N>::vs[100];
//デフォルトコンストラクターが null node になっているべき (例えば len=0)
//reverse なし
//N::push
//副作用なし,１個の子にpush
//N::clear
//lazy tagを消去
//push/lazy は AVLLAZY がdefineされてなければ呼ばれない（これ定数倍変わる？）
//N::single
//ノード単体の情報を元に部分木情報を初期化
//N::updatel,updater
//N::ok
//max_right のノリで split をする

//CF887F
//set::set iterator の要領で各ノードから erase/next/prev が呼べるようになった
//p==(np)-1 で delete 済みかどうか確認できる
//itr を保存しておいて後で呼び出すときは prep を忘れないように
//p のリンクをどうやって管理してしまうか考えたときに,upd を利用することにした
//特に upd 直後は p==nullptr であることに注意!

//TOKI35G
//beats っぽい怪しい updateを走らせた
//ある部分木全体を更新できないとき，もちろんその下に潜るのだが，
//根のノード単体に対する更新を忘れないようにする

//ノード同士の比較関数でも split 可能(TODO)
//TODO 細かい実装の違いによる定数倍を検証

struct N{
	int left,right,cut=inf;
	bool empty()const{
		return cut==inf;
	}
	int eval(int x)const{
		return x<cut?left:right;
	}
	static N merge(const N&a,const N&b){
		if(a.empty())return b;
		if(b.empty())return a;
		return N{a.eval(b.left),a.eval(b.right),b.cut};
	}
};
struct M{
	int v,b;
	pi z;
	M(){}
	M(int vv,int bb):v(vv),b(bb){single();}
	void single(){
		z.a=b;
		z.b=v-b;
	}
	static pi zmg(pi x,pi y){
		return pi(x.a+y.a,min(x.b,-x.a+y.b));
	}
	void updatel(const M&x){
		z=zmg(x.z,z);
	}
	void updater(const M&x){
		z=zmg(z,x.z);
	}
	bool operator<(const M&x)const{
		return v<x.v;
	}
};
avl<M> w(200000);
using np=avl<M>::np;
/*
struct Ms{
	vc<pi> buf;
	void init(vc<pi> vb){
		buf=vb;
	}
	void set(int i,pi vb){
		buf[i]=vb;
	}
	int query(int a){
		auto cur=buf;
		soin(cur);
		int bsum=0;
		for(auto [v,b]:cur)bsum+=b;
		rein(cur);
		for(auto [v,b]:cur){
			if(a+bsum>v)return a+bsum;
			bsum-=b;
		}
		return a;
	}
};*/
struct Ms{
	np root;
	vc<np> buf;
	void init(vc<pi> vb){
		root=nullptr;
		for(auto [v,b]:vb){
			np x=w.nn(M(v,b));
			buf.pb(x);
			w.insert(root,x);
		}
	}
	void set(int i,pi vb){
		auto x=buf[i];
		root=w.erase(x);
		w.emplace_new(x,M(vb.a,vb.b));
		w.insert(root,x);
	}
	int dfs(np x,int a){
		if(!x)return -inf;
		if(a<=x->v.z.b)return -inf;
		int lsum=0;
		if(x->l)lsum=x->l->v.z.a;
		int cur=a+lsum+x->v.b;
		int res=dfs(x->r,cur);
		if(res!=-inf)return res;
		else if(cur>x->v.v)return cur;
		else return dfs(x->l,a);
	}
	int query(int a){
		int res=dfs(root,a);
		if(res!=-inf)return res;
		else return a;
		/*auto ls=w.listup(root);
		
		int bsum=0;
		for(auto [v,b,z]:ls)bsum+=b;
		rein(ls);
		for(auto [v,b,z]:ls){
			if(a+bsum>v)return a+bsum;
			bsum-=b;
		}
		return a;*/
	}
};
//Ms: 頂点 x から伸びる light subtree の集合をデータに持つ
//segtree<M> の一般化
//N: hld の heavy-path + そこから伸びる light child の部分木すべて みたいなノード
//constructor N() 空ノード
//merge(x,y) heavy path のマージ x が親側
//gen_light この heavy path を struct M に変換する

void slv(){
	INT(n,q);
	vvc<int> trw(n);
	vi f(n,-1);
	rng(i,1,n){
		INT(p);	p--;
		f[i]=p;
		trw[p].pb(i);
	}
	VI(a,n);
	VI(b,n);
	
	HLD<int> hld(trw,0);
	const auto&t=hld.g;
	
	vi lid(n,-1);
	vc<segtree<N>> seg(n);
	vc<Ms> lch(n);
	//どの segtree のどの位置にいるか
	auto getij=[&](int v){
		int h=hld.head[v];
		return pi(h,hld.dep[v]-hld.dep[h]);
	};
	//sub[v] 及び v 本体のデータから segtree 情報を更新
	auto gen_N=[&](int v){
		int c=a[v];
		if(si(t[v]))c+=b[t[v][0]];
		int x=lch[v].query(a[v]);
		int y=lch[v].query(c);
		return N{y,x,y};
	};
	auto upd_seg=[&](int v){
		auto [i,j]=getij(v);
		seg[i].point_set(j,gen_N(v));
	};
	//v の subtree を light node として何らかのデータに圧縮
	//その後 sub[par[v]] に突っ込まれる
	auto gen_light=[&](int v){
		assert(hld.head[v]==v);
		return pi(seg[v].getall().eval(-1),b[v]);
	};
	//init
	for(auto v:reout(hld.ni)){
		{
			int s=si(hld.g[v])-1;
			if(s>=1){
				vc<pi> ls(s);
				rep(i,s){
					int to=hld.g[v][i+1];
					lid[to]=i;
					ls[i]=gen_light(to);
				}
				lch[v].init(ls);
			}
		}
		if(hld.head[v]==v){
			int s=hld.hei[v];
			vc<N> ls(s);
			rep(i,s)ls[i]=gen_N(hld.adv(v,i));
			seg[v]=segtree<N>(ls);
		}
	}
	auto get_subtree=[&](int v){
		auto [i,j]=getij(v);
		return seg[i].composite(j,seg[i].n);
	};
	
	rep(_,q){
		INT(op);
		if(op==1){
			INT(i,a_,b_);
			i--;
			a[i]=a_;
			b[i]=b_;
			
			int v=i;
			
			upd_seg(v);
			if(hld.head[v]!=v)upd_seg(hld.par[v]);
			
			while(v>=0){
				v=hld.head[v];
				int p=hld.par[v];
				if(p!=-1){
					lch[p].set(lid[v],gen_light(v));
					upd_seg(p);
				}
				v=p;
			}
		}else if(op==2){
			INT(c,d);
			c--;d--;
			
			int x=get_subtree(c).eval(-1);
			int y=get_subtree(d).eval(-1);
			
			dmp2(x,y);
			if(pi(x,c)>pi(y,d))print(0);
			else print(1);
		}else assert(0);
	}
}

signed main(signed argc,char*argv[]){
	if(argc>1&&strcmp(argv[1],"D")==0)dbg=true;
	
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	if(dbg){
		while(1){
			if(current_run_id%run_batch_size==0){
				cerr<<"Current Run "<<current_run_id<<endl;
			}
			slv();
			current_run_id++;
		}
	}else{
		//int t;cin>>t;rep(_,t)
		slv();
	}
}