#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)
const int maxn = 5e3 + 20;
map<pair<pair<int , int> , int> , bool> mp;
int n , who[maxn];
bool is[maxn];
vector<int> adj[maxn] , out[maxn] , in[maxn];
int get_dp(int mask1 , int mask2 , int v)
{
pair<pair<int , int> , int> tmp = {{mask1 , mask2} , v};
if(mp.count(tmp))
return mp[tmp];
for(auto u : adj[v])
{
int w;
if(bit(mask1 , u))
w = 1;
else if(bit(mask2 , u))
w = 0;
else
{
if(is[u])
w = get_dp(mask1 | mask2 | (1 << u) , 0 , u);
else
w = get_dp(mask1 , mask2 | (1 << u) , u);
}
if(w == who[v])
{
mp[tmp] = who[v];
return who[v];
}
}
mp[tmp] = 1 - who[v];
return 1 - who[v];
}
int DFS(int v)
{
for(auto u : adj[v])
{
int w;
if(u == v)
w = is[v];
else
w = DFS(u);
if(w == who[v])
return who[v];
}
return !who[v];
}
bool visited[maxn] , has[maxn] , wtf[maxn];
vector<int> topol , ver[maxn];
int C , color[maxn];
void dfs(int v)
{
visited[v] = 1;
for(auto u : out[v])
if(!visited[u])
dfs(u);
topol.pb(v);
}
void sfd(int v)
{
visited[v] = 1;
color[v] = C;
ver[C].pb(v);
has[color[v]] |= is[v];
for(auto u : in[v])
if(!visited[u])
sfd(u);
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
n = a.size();
bool all = 1;
for(int i = 0; i < n; i++)
{
is[i] = r[i] , who[i] = a[i];
all &= who[i];
}
bool f = 1;
for(int i = 0; i < (int)u.size(); i++)
{
f &= (v[i] - u[i] <= 1) && (v[i] >= u[i]);
adj[u[i]].pb(v[i]);
out[u[i]].pb(v[i]);
in[v[i]].pb(u[i]);
if(v[i] == u[i])
wtf[v[i]] = 1;
}
vector<int> ans;
if(n <= 15)
{
for(int i = 0; i < n; i++)
{
if(is[i])
ans.pb(get_dp(1 << i , 0 , i));
else
ans.pb(get_dp(0 , (1 << i) , i));
}
}
else if(f)
{
for(int i = 0; i < n; i++)
ans.pb(DFS(i));
}
else if(all)
{
for(int i = 0; i < n; i++)
if(!visited[i])
dfs(i);
reverse(topol.begin() , topol.end());
memset(visited , 0 , sizeof visited);
for(auto v : topol)
if(!visited[v])
{
sfd(v);
if((int)ver[C].size() == 1)
has[C] &= wtf[ver[C][0]];
C++;
}
for(int i = C - 1; i >= 0; i--)
for(auto v : ver[i])
for(auto u : out[v])
has[i] |= has[color[u]];
for(int i = 0; i < n; i++)
ans.pb(has[color[i]]);
}
else
{
for(int i = 0; i < n; i++)
if(!visited[i] && !is[i])
dfs(i);
reverse(topol.begin() , topol.end());
memset(visited , 0 , sizeof visited);
for(int i = 0; i < n; i++)
if(is[i])
visited[i] = 1;
for(auto v : topol)
if(!visited[v])
{
sfd(v);
has[C] = (ver[C].size() > 1) || (wtf[ver[C][0]]);
C++;
}
for(int i = C - 1; i >= 0; i--)
for(auto v : ver[i])
for(auto u : out[v])
if(!is[u])
has[i] |= has[color[u]];
for(int i = 0; i < n; i++)
{
if(!is[i])
is[i] = has[color[i]];
else
is[i] = 0;
}
for(int i = 0; i < C; i++)
ver[i].clear();
memset(has , 0 , sizeof has);
memset(visited , 0 , sizeof visited);
memset(color , 0 , sizeof color);
topol.clear();
C = 0;
for(int i = 0; i < n; i++)
if(!visited[i])
dfs(i);
reverse(topol.begin() , topol.end());
memset(visited , 0 , sizeof visited);
for(auto v : topol)
if(!visited[v])
{
sfd(v);
C++;
}
for(int i = C - 1; i >= 0; i--)
for(auto v : ver[i])
for(auto u : out[v])
has[i] |= has[color[u]];
for(int i = 0; i < n; i++)
ans.pb(!has[color[i]]);
}
return ans;
}
