// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define endl '\n'
#define sep ' '
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define pb push_back
#define Mp make_pair
const int maxn = 3e5 + 7;
const int maxlg = 20;
int n, m;
vector<int> adj[maxn], adjr[maxn];
int val[maxn], arr[maxn];
int p[maxn]; vector<int> ls[maxn];
vector<pair<pii, int>> E;
int mark[maxn], col[maxn], c = 0;
bool M[maxn], ok[maxn]; vector<int> vc;
vector<int> ans;
bool cmp(int i, int j) {
return (val[i] < val[j]);
}
bool is_ok(int u, int c) {
int j = lower_bound(all(ls[u]), c) - ls[u].begin();
return (j < len(ls[u]) && ls[u][j] == c);
}
void dfs(int v) {
mark[v] = 1;
for (int u : adj[v]) {
if (!mark[u]) dfs(u);
}
vc.pb(v);
}
void dfsr(int v) {
mark[v] = 1; col[v] = c;
for (int u : adjr[v]) {
if (!mark[u]) dfsr(u);
}
}
void scc() {
fill(mark, mark + n, 0); vc.clear();
for (int i = 0; i < n; i++) {
if (!mark[i]) dfs(i);
}
reverse(all(vc));
fill(mark, mark + n, 0); c = 0;
for (int i : vc) {
if (!mark[i]) {
dfsr(i); c++;
}
}
}
void fix_edges() {
for (int i = 0; i < n; i++) {
adj[i].clear(); adjr[i].clear();
ls[i].clear(); M[i] = 0;
}
for (int j = 0; j < n; j++) {
int i = arr[j];
ls[p[i]].pb(val[i]);
M[p[i]] = 1;
}
for (auto f : E) {
int u = f.F.F, v = f.F.S, c = f.S;
u = p[u]; v = p[v];
if (u == v) continue;
if (is_ok(u, c)) {
adj[u].pb(v); adjr[v].pb(u);
M[u] = 0;
}
if (is_ok(v, c)) {
adj[v].pb(u); adjr[u].pb(v);
M[v] = 0;
}
}
}
void solve() {
fix_edges();
scc();
for (int i = 0; i < n; i++) p[i] = col[p[i]];
}
int get_min() {
int mn = n; fix_edges();
for (int i = 0; i < n; i++) {
if (!M[i]) continue;
if (len(ls[i]) < mn) mn = len(ls[i]);
}
return mn;
}
vector<int> find_reachable(vector<int> rx, vector<int> ux, vector<int> vx, vector<int> cx) {
n = len(rx); m = len(ux);
for (int i = 0; i < n; i++) val[i] = rx[i];
iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
for (int i = 0; i < m; i++) {
int u = ux[i], v = vx[i], c = cx[i];
E.pb(Mp(Mp(u, v), c));
}
iota(p, p + n, 0);
for (int T = 0; T < maxlg; T++) {
solve();
}
int mn = get_min(); fill(ok, ok + n, 0);
for (int i = 0; i < n; i++) {
if (!M[i]) continue;
if (len(ls[i]) == mn) ok[i] = 1;
}
ans.clear(); ans.resize(n);
for (int i = 0; i < n; i++) ans[i] = ok[p[i]];
return ans;
}
