#include "train.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
const int lim = 5005;
vector<int>a, r, u, v, g[lim];
int n, m;
namespace sub1{
bool check_subtask(){
for(int i = 0; i < m; i++){
if(v[i] != u[i] && v[i] != u[i] + 1){
return false;
}
}
return true;
}
vector<int>solve(){
vector<int>dp(n + 1);
dp[n] = 0;
vector<vector<bool>>have(n, vector<bool>(2, false));
for(int i = 0; i < m; i++){
have[u[i]][v[i] - u[i]] = true;
}
for(int i = n - 1; i > -1; i--){
if(r[i]){
if(a[i]){
dp[i] = have[i][0] ? 1 : dp[i + 1];
}
else{
dp[i] = have[i][1] ? dp[i + 1] : 1;
}
}
else if(a[i]){
dp[i] = have[i][1] ? dp[i + 1] : 0;
}
else{
dp[i] = have[i][0] ? 0 : dp[i + 1];
}
}
dp.pop_back();
return dp;
}
}
namespace sub3{
bitset<lim>out, have_r, bs[lim];
int tdfs = 0, cnt_color = 0, num[lim], low[lim], color[lim];
vector<int>stk;
void dfs(int s){
low[s] = num[s] = ++tdfs;
stk.push_back(s);
for(int& d : g[s]){
if(!out[d]){
if(num[d] == 0){
dfs(d);
minimize(low[s], low[d]);
}
else{
minimize(low[s], num[d]);
}
}
}
if(low[s] == num[s]){
bs[cnt_color].reset();
bs[cnt_color][cnt_color] = true;
int siz = 0;
while(true){
int x = stk.back();
stk.pop_back();
siz++;
color[x] = cnt_color;
out[x] = true;
if(r[x]){
have_r[cnt_color] = true;
}
for(int& y : g[x]){
if(color[y] != -1){
bs[color[x]] |= bs[color[y]];
}
}
if(x == s){
break;
}
}
if(siz < 2 && find(g[s].begin(), g[s].end(), s) == g[s].end()){
have_r[cnt_color] = false;
}
cnt_color++;
}
}
vector<int>solve(){
for(int i = 0; i < m; i++){
g[u[i]].push_back(v[i]);
}
out.reset();
have_r.reset();
memset(num, 0, sizeof(num));
memset(color, -1, sizeof(color));
for(int i = 0; i < n; i++){
if(num[i] == 0){
dfs(i);
}
}
vector<int>ans(n, 0);
for(int i = 0; i < n; i++){
for(int j = 0; j < cnt_color; j++){
if(have_r[j] && bs[color[i]][j]){
ans[i] = 1;
break;
}
}
}
return ans;
}
}
namespace sub4{
bitset<lim>vis, cyc, have_cyc, bs[lim];
bool dfs_1(const int root, int s){
vis[s] = true;
for(int& d : g[s]){
if(!r[d] && (d == root || (!vis[d] && dfs_1(root, d)))){
return true;
}
}
return false;
}
int tdfs = 0, cnt_color = 0, num[lim], low[lim], color[lim];
vector<int>stk;
void dfs_2(int s){
low[s] = num[s] = ++tdfs;
stk.push_back(s);
for(int& d : g[s]){
if(!vis[d]){
if(num[d] == 0){
dfs_2(d);
minimize(low[s], low[d]);
}
else{
minimize(low[s], num[d]);
}
}
}
if(low[s] == num[s]){
bs[cnt_color].reset();
bs[cnt_color][cnt_color] = true;
while(true){
int x = stk.back();
stk.pop_back();
color[x] = cnt_color;
vis[x] = true;
if(cyc[x]){
have_cyc[cnt_color] = true;
}
for(int& y : g[x]){
if(color[y] != -1){
bs[color[x]] |= bs[color[y]];
}
}
if(x == s){
break;
}
}
cnt_color++;
}
}
vector<int>solve(){
for(int i = 0; i < m; i++){
g[u[i]].push_back(v[i]);
}
cyc.reset();
for(int i = 0; i < n; i++){
if(!r[i]){
vis.reset();
cyc[i] = dfs_1(i, i);
}
}
memset(num, 0, sizeof(num));
memset(color, -1, sizeof(color));
vis.reset();
for(int i = 0; i < n; i++){
if(num[i] == 0){
dfs_2(i);
}
}
vector<int>ans(n, 1);
for(int i = 0; i < n; i++){
for(int j = 0; j < cnt_color; j++){
if(have_cyc[j] && bs[color[i]][j]){
ans[i] = 0;
break;
}
}
}
return ans;
}
}
namespace sub256{
vector<int>solve(){
vector<int>out_deg(n, 0), ans(n);
for(int i = 0; i < m; i++){
g[v[i]].push_back(u[i]);
out_deg[u[i]]++;
}
while(true){
queue<int>q;
vector<int>deg(n);
for(int i = 0; i < n; ans[i++] = 0){
deg[i] = a[i] ? 1 : out_deg[i];
if(r[i] == 1){
q.push(i);
}
}
while(!q.empty()){
int s = q.front();
q.pop();
for(int& d : g[s]){
if(--deg[d] == 0){
ans[d] = 1;
if(r[d] == 0){
q.push(d);
}
}
}
}
bool flag = true;
for(int i = 0; i < n; i++){
if(r[i] == 1 && ans[i] == 0){
r[i] = 0;
flag = false;
}
}
if(flag){
break;
}
}
return ans;
}
}
vector<int>who_wins(vector<int>_a, vector<int>_r, vector<int>_u, vector<int>_v){
swap(a, _a);
swap(r, _r);
swap(u, _u);
swap(v, _v);
n = a.size();
m = u.size();
if(sub1::check_subtask()){
return sub1::solve();
}
if(find(a.begin(), a.end(), 0) == a.end()){
return sub3::solve();
}
if(find(a.begin(), a.end(), 1) == a.end()){
return sub4::solve();
}
return sub256::solve();
}
