#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=3e5+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n,fau[N],m;
bool ok[N],vis[N],vis2[N];
vi kt[N],dk[N],curr;
vector<pair<int,int> >graf[N];
set<int> dos[N];
set<pair<int,int>> zab[N];
void Union(int a,int b){
a=fau[a],b=fau[b];
if(a==b) return;
if(kt[a].size()>kt[b].size()) swap(a,b);
for(auto v:kt[a]) dos[b].insert(t[v]),fau[v]=b;
dos[a].clear(),zab[a].clear();
ok[b]&=ok[a];
for(auto v:kt[a]){
kt[b].push_back(v);
for(auto [u,c]:graf[v]){
auto it=dos[b].lower_bound(c);
if(it!=dos[b].end() and (*it)==c){
dk[b].push_back(u);
}else zab[b].insert({c,u});
}
auto it=zab[b].lower_bound({t[v],0});
while(it!=zab[b].end() and (*it).fi==t[v]){
dk[b].push_back((*it).se);
zab[b].erase(it);
it=zab[b].lower_bound({t[v],0});
}
}
kt[a].clear();
}
void dfs(int v){
vis[v]=1;
vis2[v]=1;
curr.push_back(v);
while(dk[fau[v]].size()){
int u=dk[fau[v]].back();
dk[fau[v]].pop_back();
if(vis[u] and !vis2[u]){
ok[fau[v]]=0;
continue;
}
if(vis[u]){
while(curr.size() and fau[curr.back()]!=fau[u]){
Union(u,curr.back());
curr.pop_back();
}
}else{
dfs(u);
if(fau[v]!=fau[u]) ok[fau[v]]=0;
}
}
if(curr.size() and curr.back()==v)
curr.pop_back();
vis2[v]=0;
}
vi find_reachable(vi pom1,vi pom2,vi pom3,vi pom4){
int n=pom1.size(),m=pom2.size();
iota(fau,fau+1+n,0);
for(int i=1;i<=n;i++){
t[i]=pom1[i-1];
t[i]++;
ok[i]=1;
dos[i].insert(t[i]);
kt[i].push_back(i);
}
for(int i=1;i<=m;i++){
int a,b,c;
a=pom2[i-1],b=pom3[i-1],c=pom4[i-1];
c++,a++,b++;
graf[a].push_back({b,c}),graf[b].push_back({a,c});
if(c==t[a]) dk[a].push_back(b);
else zab[a].insert({c,b});
if(c==t[b]) dk[b].push_back(a);
else zab[b].insert({c,a});
}
for(int i=1;i<=n;i++){
if(!vis[i]) dfs(i);
}
int mini=INFi;
for(int i=1;i<=n;i++){
if(ok[fau[i]])
mini=min(mini,(int)kt[fau[i]].size());
}
vi res;
for(int i=1;i<=n;i++){
if(!ok[fau[i]] or mini<kt[fau[i]].size()) res.push_back(0);
else res.push_back(1);
}
return res;
}
