#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 300000, M = 300000, C = 30, INF = 0x3f3f3f3f;
int ii[M], jj[M], bb[M];
int *eh[N][C], eo[N][C], eo_[N][C]; char available[N][C];
void append(int i, int h) {
int c = bb[h], o = eo[i][c]++;
if (o == eo_[i][c])
eh[i][c] = (int *) realloc(eh[i][c], (eo_[i][c] *= 2) * sizeof *eh[i]);
eh[i][c][o] = h;
}
int ds[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
int ds_[N];
int find_(int i) {
return ds_[i] < 0 ? i : (ds_[i] = find_(ds_[i]));
}
void merge(int i, int j) {
int c, o;
for (c = 0; c < C; c++) {
available[i][c] |= available[j][c];
for (o = eo[j][c]; o--; )
append(i, eh[j][c][o]);
free(eh[j][c]);
}
}
void join_(int i, int j) {
int tmp;
i = find_(i);
j = find_(j);
if (i == j)
return;
if (ds_[i] > ds_[j])
tmp = i, i = j, j = tmp;
ds_[i] += ds_[j], ds_[j] = i, merge(i, j);
}
int pp[N], qu[N], cnt;
void get(int i) {
int c, o;
pp[i] = -1;
for (c = 0; c < C; c++)
if (available[i][c])
while (eo[i][c]) {
int h = eh[i][c][--eo[i][c]], j = i ^ find_(ii[h]) ^ find_(jj[h]);
if (j != i) {
pp[i] = j;
if (!join(i, j))
qu[cnt++] = i;
return;
}
}
}
vi find_reachable(vi aa, vi ii_, vi jj_, vi bb_) {
int n = aa.size(), m = ii_.size(), h, i, j, c, mn;
vi ans(n);
for (i = 0; i < n; i++)
for (c = 0; c < C; c++)
eh[i][c] = (int *) malloc((eo_[i][c] = 2) * sizeof *eh[i][c]);
for (h = 0; h < m; h++)
ii[h] = ii_[h], jj[h] = jj_[h], bb[h] = bb_[h];
for (i = 0; i < n; i++)
available[i][aa[i]] = 1;
for (h = 0; h < m; h++)
append(ii[h], h), append(jj[h], h);
memset(ds, -1, n * sizeof *ds), memset(ds_, -1, n * sizeof *ds_);
for (i = 0; i < n; i++)
get(i);
while (cnt--) {
i = qu[cnt];
for (j = pp[i]; j != i; j = pp[j])
join_(i, j);
get(find_(i));
}
mn = INF;
for (i = 0; i < n; i++)
if (ds_[i] < 0 && pp[i] == -1)
mn = min(mn, -ds_[i]);
for (i = 0; i < n; i++)
ans[i] = pp[find_(i)] == -1 && -ds_[find_(i)] == mn;
return ans;
}
