#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i= (a); i < (b); i++)
#define per(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#ifdef LOCAL
template<class A, class B> auto& operator<<(auto &o, pair<A, B> p) { return o << '(' << p.x << ", " << p.y << ')'; }
auto& operator<<(auto& o, auto a) {
o << "{";
for (auto b : a) o << b << ", ";
return o << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << "\n"; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) ;
#endif
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const long int SEED = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
const int MAXN = 3e5 + 5;
int n;
vi r;
map<int, vi> g[MAXN];
set<int> ready[MAXN], all_keys[MAXN];
void ins_edge(map<int,vi>& M, int c, int dst) {
if (!M.count(c)) {
M[c] = vi();
}
M[c].eb(dst);
}
bool check_empty(map<int,vi>& M, int c) {
if (!M.count(c)) return true;
return M[c].empty();
}
int vis[MAXN], reachable[MAXN];
int f[MAXN], cnt[MAXN];
int find(int x) {
if (f[x] != x) f[x] = find(f[x]);
return f[x];
}
bool unite(int x, int y) {
x = find(x); y = find(y);
assert(vis[x] == 1 && vis[y] == 1);
if (x == y) return false;
if (cnt[x] < cnt[y]) swap(x,y);
f[y] = x;
cnt[x] += cnt[y];
cnt[y] = 0;
for (int i: ready[y]) {
ready[x].insert(i);
}
ready[y].clear();
for (auto& [c, vec]: g[y]) {
for (int i: vec) {
ins_edge(g[x], c, i);
if (all_keys[x].count(c)) {
ready[x].insert(c);
}
}
}
g[y].clear();
for (int i: all_keys[y]) {
all_keys[x].insert(i);
if (!check_empty(g[x], i)) {
ready[x].insert(i);
}
}
all_keys[y].clear();
return true;
}
void solve(int x) {
debug("solve", x);
vi vec = {x};
vis[x] = 1;
while (!vec.empty()) {
int cur = vec.back();
debug(cur, find(cur));
cur = find(cur);
debug(ready[cur]);
if (ready[cur].empty()) {
debug("ready empty");
debug("final node representant candidate", cur, cnt[cur]);
reachable[cur] = cnt[cur];
vis[cur] = 2;
vec.pop_back();
break;
}
int c = *ready[cur].begin();
debug(c);
vi &neigh = g[cur][c];
debug(neigh);
if (neigh.empty()) {
debug("neigh empty");
ready[cur].erase(c);
continue;
}
int nxt = neigh.back();
neigh.pop_back();
debug(nxt, find(nxt));
nxt = find(nxt);
if (!vis[nxt]) {
debug("append", nxt);
vis[nxt] = 1;
vec.eb(nxt);
}
else if (vis[nxt] == 2) {
debug("current stack is not in final set", vec);
break;
}
else if (vis[nxt] == 1) {
debug("unite+");
while (find(vec.back()) != find(nxt)) {
debug(vec.back(), nxt);
unite(vec.back(), nxt);
vec.pop_back();
}
debug("unite-");
}
else {
debug("vis kinda weird", nxt, vis[nxt]);
assert(false);
}
}
debug("while finished", vec);
for (int i: vec) {
vis[find(i)] = 2;
}
}
void init() {
rep(i,0,n) {
f[i] = i;
cnt[i] = 1;
}
}
vi find_reachable(vi _r, vi u, vi v, vi c) {
n = sz(_r);
init();
r = _r;
rep(i,0,sz(u)) {
ins_edge(g[u[i]], c[i], v[i]);
ins_edge(g[v[i]], c[i], u[i]);
}
rep(i,0,n) {
ready[i].insert(r[i]);
all_keys[i].insert(r[i]);
reachable[i] = n + 1;
}
rep(i,0,n) {
if (!vis[find(i)]) {
solve(find(i));
}
}
vi ans(n);
int min_reachable = n;
rep(i,0,n) {
ckmin(min_reachable, reachable[i]);
}
rep(i,0,n) {
ans[i] = (reachable[find(i)] == min_reachable?1:0);
}
return ans;
}
#ifdef LOCAL
int main() {
int _n, _m; cin>>_n>>_m;
vi _r(_n), _u(_m), _v(_m), _c(_m);
rep(i,0,_n) {
cin>>_r[i];
}
rep(i,0,_m) {
cin>>_u[i];
}
rep(i,0,_m) {
cin>>_v[i];
}
rep(i,0,_m) {
cin>>_c[i];
}
vi ANSWER = find_reachable(_r, _u, _v, _c);
debug(ANSWER);
}
#endif
