Submission #915282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915282	2024-01-23T15:42:54 Z	maroonrk	Beech Tree (IOI23_beechtree)	C++17	17 / 100	320 ms	157972 KB

beechtree

#include "beechtree.h"

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

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

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

//mint107 は verify してねえ
//#define DYNAMIC_MOD

struct modinfo{uint mod,root;
#ifdef DYNAMIC_MOD
constexpr modinfo(uint m,uint r):mod(m),root(r),im(0){set_mod(m);}
ull im;
constexpr void set_mod(uint m){
	mod=m;
	im=ull(-1)/m+1;
}
uint product(uint a,uint b)const{
	ull z=ull(a)*b;
	uint x=((unsigned __int128)z*im)>>64;
	uint v=uint(z)-x*mod;
	return v<mod?v:v+mod;
}
#endif
};
template<modinfo const&ref>
struct modular{
	static constexpr uint const &mod=ref.mod;
	static modular root(){return modular(ref.root);}
	uint v;
	//modular(initializer_list<uint>ls):v(*ls.bg){}
	modular(ll vv=0){s(vv%mod+mod);}
	modular& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	modular operator-()const{return modular()-*this;}
	modular& operator+=(const modular&rhs){return s(v+rhs.v);}
	modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);}
	modular&operator*=(const modular&rhs){
		#ifndef DYNAMIC_MOD
		v=ull(v)*rhs.v%mod;
		#else
		v=ref.product(v,rhs.v);
		#endif
		return *this;
	}
	modular&operator/=(const modular&rhs){return *this*=rhs.inv();}
	modular operator+(const modular&rhs)const{return modular(*this)+=rhs;}
	modular operator-(const modular&rhs)const{return modular(*this)-=rhs;}
	modular operator*(const modular&rhs)const{return modular(*this)*=rhs;}
	modular operator/(const modular&rhs)const{return modular(*this)/=rhs;}
	modular pow(ll n)const{
		if(n<0)return inv().pow(-n);
		modular res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modular inv()const{return pow(mod-2);}
	/*modular inv()const{
		int x,y;
		int g=extgcd<ll>(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return modular(x);
	}*/
	friend modular operator+(ll x,const modular&y){
		return modular(x)+y;
	}
	friend modular operator-(ll x,const modular&y){
		return modular(x)-y;
	}
	friend modular operator*(ll x,const modular&y){
		return modular(x)*y;
	}
	friend modular operator/(ll x,const modular&y){
		return modular(x)/y;
	}
	friend ostream& operator<<(ostream&os,const modular&m){
		return os<<m.v;
	}
	friend istream& operator>>(istream&is,modular&m){
		ll x;is>>x;
		m=modular(x);
		return is;
	}
	bool operator<(const modular&r)const{return v<r.v;}
	bool operator==(const modular&r)const{return v==r.v;}
	bool operator!=(const modular&r)const{return v!=r.v;}
	explicit operator bool()const{
		return v;
	}
};

#ifndef DYNAMIC_MOD
//extern constexpr modinfo base{998244353,3};
//extern constexpr modinfo base{1000000007,0};
extern constexpr modinfo base{2147483579,1689685080};//2^31 未満の最大の安全素数
//modinfo base{1,0};
#ifdef USE_GOOD_MOD
static_assert(base.mod==998244353);
#endif
#else
modinfo base(1,0);
extern constexpr modinfo base107(1000000007,0);
using mint107=modular<base107>;
#endif
using mint=modular<base>;

mint parity(int i){
	return i%2==0?1:-1;
}

#ifdef LOCAL
const int vmax=10010;
#else
const int vmax=(1<<21)+10;
#endif
mint fact[vmax],finv[vmax],invs[vmax];
void initfact(){
	fact[0]=1;
	rng(i,1,vmax){
		fact[i]=fact[i-1]*i;
	}
	finv[vmax-1]=fact[vmax-1].inv();
	for(int i=vmax-2;i>=0;i--){
		finv[i]=finv[i+1]*(i+1);
	}
	for(int i=vmax-1;i>=1;i--){
		invs[i]=finv[i]*fact[i-1];
	}
}
mint choose(int n,int k){
	return inc(0,k,n)?fact[n]*finv[n-k]*finv[k]:0;
}
mint binom(int a,int b){
	return 0<=a&&0<=b?fact[a+b]*finv[a]*finv[b]:0;
}
mint catalan(int n){
	return binom(n,n)-(n-1>=0?binom(n-1,n+1):0);
}
//対角線を超えず (x,y) に至る方法の数
mint catalan(int x,int y){
	assert(y<=x);
	return binom(x,y)-binom(x+1,y-1);
}
//y=x+c を超えず (x,y) に至る方法の数
mint catalan(int x,int y,int c){
	assert(y<=x+c);
	return binom(x,y)-binom(x+c+1,y-c-1);
}

/*
const int vmax=610;
mint fact[vmax+1],binbuf[vmax+1][vmax+1];
mint choose(int n,int k){
	return 0<=k&&k<=n?binbuf[n-k][k]:0;
}
mint binom(int a,int b){
	return 0<=a&&0<=b?binbuf[a][b]:0;
}
void initfact(int n){
	fact[0]=1;
	rep(i,n)fact[i+1]=fact[i]*(i+1);
	rep(i,n+1)rep(j,n+1){
		if(i==0&&j==0){
			binbuf[i][j]=1;
		}else{
			binbuf[i][j]=0;
			if(i)binbuf[i][j]+=binbuf[i-1][j];
			if(j)binbuf[i][j]+=binbuf[i][j-1];
		}
	}
}
*/

mint p2[vmax],p2inv[vmax];
void initp2(){
	p2[0]=1;
	rep(i,vmax-1)p2[i+1]=p2[i]*2;
	p2inv[vmax-1]=p2[vmax-1].inv();
	per(i,vmax-1)p2inv[i]=p2inv[i+1]*2;
}

bool dbg=false;

//内部でグラフをいじるから 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);
	}
};

//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);
	}
	//UTPC2020E
	template <class F,class... Args> 
	pair<int,N> min_left(int r,F f,Args&&... args){
		assert((N().*f)(forward<Args>(args)...));
		assert(0<=r&&r<=n);
        if(r==0)return mp(0,N());
        r+=s;
        N sm;
        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);
    }
    //行列とか乗せて必要なのはベクトルとの積，みたいなときに使える？
    //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;
	}
};

//max版
struct PreMax{
	int len,sum,pos,val;
	PreMax():len(0),sum(0),pos(0),val(0){}
	PreMax(int v):len(1),sum(v){
		single();
	}
	void single(){
		if(sum>0){
			pos=1;
			val=sum;
		}else{
			pos=0;
			val=0;
		}
	}
	static PreMax merge(const PreMax&a,const PreMax&b){
		PreMax res;
		res.len=a.len+b.len;
		res.sum=a.sum+b.sum;
		if(a.val>=a.sum+b.val){
			res.pos=a.pos;
			res.val=a.val;
		}else{
			res.pos=a.len+b.pos;
			res.val=a.sum+b.val;
		}
		return res;
	}
	void add(int v){
		assert(len==1);
		sum+=v;
		single();
	}
};

struct Z{
	int n;
	segtree<PreMax> seg;
	//vc<set<mint>> buf;
	//map<mint,int> pos;
	vc<unordered_set<uint>> buf;
	unordered_map<uint,int> pos;
	void init(int nn){
		n=nn;
		seg=segtree<PreMax>(vi(n,-1));
		buf.resize(n);
	}
	void modifyseg(int i){
		seg.point_set(i,si(buf[i])-1);
	}
	void upd(uint v,int s){
		auto itr=pos.find(v);
		if(itr!=pos.ed){
			if(itr->b<=s)return;
			buf[itr->b].erase(v);
			modifyseg(itr->b);
			pos.erase(itr);
		}
		pos[v]=s;
		buf[s].insert(v);
		modifyseg(s);
	}
	void collect(int l,int r,mint c,vc<mint>&ls){
		rng(i,l,r)for(auto v:buf[i])ls.pb(c+base.root*v);
	}
	void moveto(Z&z){
		for(auto [v,i]:pos)z.upd(v,i);
	}
	bool isok(){
		return seg.getall().val<=0;
	}
};

struct E{
	int to,col;
	operator int()const{
		return to;
	}
};

std::vector<int> beechtree(int n,int,std::vector<int> P,std::vector<int> C){
	vi ans(n,1);
	vvc<E> t(n);
	rng(i,1,n){
		t[P[i]].pb({i,C[i]});
	}
	HLD<E> hld(t,0);
	vc<Z> z(n);
	rep(i,n)if(hld.head[i]==i)z[i].init(hld.sub[i]);
	per(i,n){
		{
			vi tmp;
			for(auto [j,c]:t[i]){
				ans[i]&=ans[j];
				tmp.pb(c);
			}
			ans[i]&=isuni(tmp);
		}
		if(ans[i]){
			int h=hld.head[i];
			if(t[i].empty()){
				z[h].upd(0,0);
			}else{
				{
					vc<mint> ls;
					for(auto [j,c]:t[i]){
						int ign=0;
						for(auto [k,d]:t[j])if(c==d)ign=hld.sub[k];
						z[hld.head[j]].collect(ign,hld.sub[j],c,ls);
					}
					for(auto v:ls)
						z[h].upd(v.v,hld.sub[i]-1);
				}
				for(auto [j,c]:t[i])if(hld.head[j]==j){
					z[j].moveto(z[h]);
					z[j]=Z();
				}
			}
			ans[i]=z[h].isok();
		}
	}
	
    return ans;
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41292 KB	Output is correct
2	Correct	25 ms	41308 KB	Output is correct
3	Correct	24 ms	41296 KB	Output is correct

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41308 KB	Output is correct
2	Correct	24 ms	41304 KB	Output is correct
3	Correct	24 ms	41484 KB	Output is correct
4	Correct	25 ms	41300 KB	Output is correct
5	Correct	24 ms	41312 KB	Output is correct
6	Correct	25 ms	41320 KB	Output is correct
7	Correct	26 ms	41304 KB	Output is correct
8	Correct	25 ms	41332 KB	Output is correct
9	Correct	25 ms	41308 KB	Output is correct
10	Correct	25 ms	41308 KB	Output is correct
11	Correct	25 ms	41304 KB	Output is correct
12	Correct	24 ms	41304 KB	Output is correct
13	Correct	26 ms	41316 KB	Output is correct
14	Correct	27 ms	41284 KB	Output is correct
15	Correct	24 ms	41308 KB	Output is correct
16	Correct	24 ms	41308 KB	Output is correct
17	Correct	25 ms	41324 KB	Output is correct
18	Correct	24 ms	41456 KB	Output is correct
19	Correct	25 ms	41296 KB	Output is correct
20	Correct	26 ms	41300 KB	Output is correct
21	Correct	24 ms	41308 KB	Output is correct
22	Correct	26 ms	41308 KB	Output is correct
23	Correct	24 ms	41308 KB	Output is correct
24	Correct	24 ms	41308 KB	Output is correct
25	Correct	25 ms	41308 KB	Output is correct
26	Correct	25 ms	41308 KB	Output is correct
27	Correct	25 ms	41308 KB	Output is correct
28	Correct	25 ms	41296 KB	Output is correct
29	Correct	25 ms	41296 KB	Output is correct
30	Correct	24 ms	41304 KB	Output is correct
31	Correct	25 ms	41456 KB	Output is correct
32	Correct	24 ms	41308 KB	Output is correct
33	Correct	24 ms	41300 KB	Output is correct
34	Correct	24 ms	41296 KB	Output is correct

Subtask #2

0.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41308 KB	Output is correct
2	Correct	24 ms	41304 KB	Output is correct
3	Correct	24 ms	41484 KB	Output is correct
4	Correct	25 ms	41300 KB	Output is correct
5	Correct	24 ms	41312 KB	Output is correct
6	Correct	25 ms	41320 KB	Output is correct
7	Correct	142 ms	129604 KB	Output is correct
8	Correct	135 ms	129324 KB	Output is correct
9	Correct	25 ms	41460 KB	Output is correct
10	Incorrect	25 ms	41556 KB	2nd lines differ - on the 150th token, expected: '0', found: '1'
11	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	41304 KB	Output is correct
2	Correct	25 ms	41564 KB	Output is correct
3	Correct	27 ms	41596 KB	Output is correct
4	Correct	25 ms	41320 KB	Output is correct
5	Correct	25 ms	41564 KB	Output is correct
6	Correct	25 ms	41656 KB	Output is correct
7	Correct	25 ms	41472 KB	Output is correct
8	Correct	24 ms	41564 KB	Output is correct
9	Correct	24 ms	41304 KB	Output is correct
10	Correct	25 ms	41296 KB	Output is correct
11	Correct	30 ms	42324 KB	Output is correct
12	Correct	26 ms	42060 KB	Output is correct
13	Correct	27 ms	42340 KB	Output is correct
14	Correct	26 ms	42320 KB	Output is correct
15	Correct	223 ms	128188 KB	Output is correct
16	Correct	213 ms	122904 KB	Output is correct
17	Incorrect	230 ms	123956 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
18	Halted	0 ms	0 KB	-

Subtask #4

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41308 KB	Output is correct
2	Correct	24 ms	41304 KB	Output is correct
3	Correct	26 ms	41304 KB	Output is correct
4	Correct	25 ms	41332 KB	Output is correct
5	Correct	142 ms	129604 KB	Output is correct
6	Correct	135 ms	129324 KB	Output is correct
7	Correct	24 ms	41572 KB	Output is correct
8	Correct	26 ms	41556 KB	Output is correct
9	Correct	30 ms	42576 KB	Output is correct
10	Correct	27 ms	42488 KB	Output is correct
11	Correct	320 ms	157972 KB	Output is correct
12	Correct	277 ms	152736 KB	Output is correct

Subtask #5

0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41292 KB	Output is correct
2	Correct	25 ms	41308 KB	Output is correct
3	Correct	24 ms	41296 KB	Output is correct
4	Correct	24 ms	41308 KB	Output is correct
5	Correct	24 ms	41304 KB	Output is correct
6	Correct	24 ms	41484 KB	Output is correct
7	Correct	25 ms	41300 KB	Output is correct
8	Correct	24 ms	41312 KB	Output is correct
9	Correct	25 ms	41320 KB	Output is correct
10	Correct	26 ms	41304 KB	Output is correct
11	Correct	25 ms	41332 KB	Output is correct
12	Correct	25 ms	41308 KB	Output is correct
13	Correct	25 ms	41308 KB	Output is correct
14	Correct	25 ms	41304 KB	Output is correct
15	Correct	24 ms	41304 KB	Output is correct
16	Correct	26 ms	41316 KB	Output is correct
17	Correct	27 ms	41284 KB	Output is correct
18	Correct	24 ms	41308 KB	Output is correct
19	Correct	24 ms	41308 KB	Output is correct
20	Correct	25 ms	41324 KB	Output is correct
21	Correct	24 ms	41456 KB	Output is correct
22	Correct	25 ms	41296 KB	Output is correct
23	Correct	26 ms	41300 KB	Output is correct
24	Correct	24 ms	41308 KB	Output is correct
25	Correct	26 ms	41308 KB	Output is correct
26	Correct	24 ms	41308 KB	Output is correct
27	Correct	24 ms	41308 KB	Output is correct
28	Correct	25 ms	41308 KB	Output is correct
29	Correct	25 ms	41308 KB	Output is correct
30	Correct	25 ms	41308 KB	Output is correct
31	Correct	25 ms	41296 KB	Output is correct
32	Correct	25 ms	41296 KB	Output is correct
33	Correct	24 ms	41304 KB	Output is correct
34	Correct	25 ms	41456 KB	Output is correct
35	Correct	24 ms	41308 KB	Output is correct
36	Correct	24 ms	41300 KB	Output is correct
37	Correct	24 ms	41296 KB	Output is correct
38	Correct	25 ms	41460 KB	Output is correct
39	Incorrect	25 ms	41556 KB	2nd lines differ - on the 150th token, expected: '0', found: '1'
40	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41308 KB	Output is correct
2	Correct	24 ms	41304 KB	Output is correct
3	Correct	26 ms	41304 KB	Output is correct
4	Correct	25 ms	41332 KB	Output is correct
5	Correct	25 ms	41308 KB	Output is correct
6	Correct	25 ms	41308 KB	Output is correct
7	Correct	25 ms	41304 KB	Output is correct
8	Correct	24 ms	41304 KB	Output is correct
9	Correct	26 ms	41316 KB	Output is correct
10	Correct	27 ms	41284 KB	Output is correct
11	Correct	24 ms	41308 KB	Output is correct
12	Correct	24 ms	41308 KB	Output is correct
13	Correct	25 ms	41324 KB	Output is correct
14	Correct	24 ms	41456 KB	Output is correct
15	Correct	25 ms	41296 KB	Output is correct
16	Correct	26 ms	41300 KB	Output is correct
17	Correct	24 ms	41308 KB	Output is correct
18	Correct	26 ms	41308 KB	Output is correct
19	Correct	24 ms	41308 KB	Output is correct
20	Correct	24 ms	41308 KB	Output is correct
21	Correct	25 ms	41308 KB	Output is correct
22	Correct	25 ms	41308 KB	Output is correct
23	Correct	25 ms	41308 KB	Output is correct
24	Correct	25 ms	41296 KB	Output is correct
25	Correct	25 ms	42332 KB	Output is correct
26	Incorrect	26 ms	42432 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
27	Halted	0 ms	0 KB	-

Subtask #7

0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41292 KB	Output is correct
2	Correct	25 ms	41308 KB	Output is correct
3	Correct	24 ms	41296 KB	Output is correct
4	Correct	24 ms	41308 KB	Output is correct
5	Correct	24 ms	41304 KB	Output is correct
6	Correct	24 ms	41484 KB	Output is correct
7	Correct	25 ms	41300 KB	Output is correct
8	Correct	24 ms	41312 KB	Output is correct
9	Correct	25 ms	41320 KB	Output is correct
10	Correct	26 ms	41304 KB	Output is correct
11	Correct	25 ms	41332 KB	Output is correct
12	Correct	25 ms	41308 KB	Output is correct
13	Correct	25 ms	41308 KB	Output is correct
14	Correct	25 ms	41304 KB	Output is correct
15	Correct	24 ms	41304 KB	Output is correct
16	Correct	26 ms	41316 KB	Output is correct
17	Correct	27 ms	41284 KB	Output is correct
18	Correct	24 ms	41308 KB	Output is correct
19	Correct	24 ms	41308 KB	Output is correct
20	Correct	25 ms	41324 KB	Output is correct
21	Correct	24 ms	41456 KB	Output is correct
22	Correct	25 ms	41296 KB	Output is correct
23	Correct	26 ms	41300 KB	Output is correct
24	Correct	24 ms	41308 KB	Output is correct
25	Correct	26 ms	41308 KB	Output is correct
26	Correct	24 ms	41308 KB	Output is correct
27	Correct	24 ms	41308 KB	Output is correct
28	Correct	25 ms	41308 KB	Output is correct
29	Correct	25 ms	41308 KB	Output is correct
30	Correct	25 ms	41308 KB	Output is correct
31	Correct	25 ms	41296 KB	Output is correct
32	Correct	25 ms	41296 KB	Output is correct
33	Correct	24 ms	41304 KB	Output is correct
34	Correct	25 ms	41456 KB	Output is correct
35	Correct	24 ms	41308 KB	Output is correct
36	Correct	24 ms	41300 KB	Output is correct
37	Correct	24 ms	41296 KB	Output is correct
38	Correct	25 ms	41460 KB	Output is correct
39	Incorrect	25 ms	41556 KB	2nd lines differ - on the 150th token, expected: '0', found: '1'
40	Halted	0 ms	0 KB	-

Subtask #8

0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41308 KB	Output is correct
2	Correct	24 ms	41304 KB	Output is correct
3	Correct	26 ms	41304 KB	Output is correct
4	Correct	25 ms	41332 KB	Output is correct
5	Correct	25 ms	41308 KB	Output is correct
6	Correct	25 ms	41308 KB	Output is correct
7	Correct	25 ms	41304 KB	Output is correct
8	Correct	24 ms	41304 KB	Output is correct
9	Correct	26 ms	41316 KB	Output is correct
10	Correct	27 ms	41284 KB	Output is correct
11	Correct	24 ms	41308 KB	Output is correct
12	Correct	24 ms	41308 KB	Output is correct
13	Correct	25 ms	41324 KB	Output is correct
14	Correct	24 ms	41456 KB	Output is correct
15	Correct	25 ms	41296 KB	Output is correct
16	Correct	26 ms	41300 KB	Output is correct
17	Correct	24 ms	41308 KB	Output is correct
18	Correct	26 ms	41308 KB	Output is correct
19	Correct	24 ms	41308 KB	Output is correct
20	Correct	24 ms	41308 KB	Output is correct
21	Correct	25 ms	41308 KB	Output is correct
22	Correct	25 ms	41308 KB	Output is correct
23	Correct	25 ms	41308 KB	Output is correct
24	Correct	25 ms	41296 KB	Output is correct
25	Correct	25 ms	42332 KB	Output is correct
26	Incorrect	26 ms	42432 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
27	Halted	0 ms	0 KB	-

Subtask #9

0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	41292 KB	Output is correct
2	Correct	25 ms	41308 KB	Output is correct
3	Correct	24 ms	41296 KB	Output is correct
4	Correct	24 ms	41308 KB	Output is correct
5	Correct	24 ms	41304 KB	Output is correct
6	Correct	24 ms	41484 KB	Output is correct
7	Correct	25 ms	41300 KB	Output is correct
8	Correct	24 ms	41312 KB	Output is correct
9	Correct	25 ms	41320 KB	Output is correct
10	Correct	26 ms	41304 KB	Output is correct
11	Correct	25 ms	41332 KB	Output is correct
12	Correct	25 ms	41308 KB	Output is correct
13	Correct	25 ms	41308 KB	Output is correct
14	Correct	25 ms	41304 KB	Output is correct
15	Correct	24 ms	41304 KB	Output is correct
16	Correct	26 ms	41316 KB	Output is correct
17	Correct	27 ms	41284 KB	Output is correct
18	Correct	24 ms	41308 KB	Output is correct
19	Correct	24 ms	41308 KB	Output is correct
20	Correct	25 ms	41324 KB	Output is correct
21	Correct	24 ms	41456 KB	Output is correct
22	Correct	25 ms	41296 KB	Output is correct
23	Correct	26 ms	41300 KB	Output is correct
24	Correct	24 ms	41308 KB	Output is correct
25	Correct	26 ms	41308 KB	Output is correct
26	Correct	24 ms	41308 KB	Output is correct
27	Correct	24 ms	41308 KB	Output is correct
28	Correct	25 ms	41308 KB	Output is correct
29	Correct	25 ms	41308 KB	Output is correct
30	Correct	25 ms	41308 KB	Output is correct
31	Correct	25 ms	41296 KB	Output is correct
32	Correct	25 ms	41296 KB	Output is correct
33	Correct	24 ms	41304 KB	Output is correct
34	Correct	25 ms	41456 KB	Output is correct
35	Correct	24 ms	41308 KB	Output is correct
36	Correct	24 ms	41300 KB	Output is correct
37	Correct	24 ms	41296 KB	Output is correct
38	Correct	142 ms	129604 KB	Output is correct
39	Correct	135 ms	129324 KB	Output is correct
40	Correct	25 ms	41460 KB	Output is correct
41	Incorrect	25 ms	41556 KB	2nd lines differ - on the 150th token, expected: '0', found: '1'
42	Halted	0 ms	0 KB	-