#include "circuit.h"
//#include<stub.cpp>
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0; i< n; i++)
#define mp make_pair
using namespace std;
vector<signed> par;
vector<signed> state;
vector<vi> adj;
int n,m;
const int mod = 1e9 + 2022;
const int mxn = 2e5 + 5;
vi dep(mxn);
vi cont(mxn);
vi chil(mxn);
int binexp(int a, int b){
int ret = 1;
f0r(i, 30){
if(b & (1 << i)){
ret *= a;
ret %= mod;
}
a *= a;
a %= mod;
}
return ret;
}
vi tl(mxn * 2);
vi tr(mxn * 2);
vi tree(mxn * 2);
vi totcont(mxn * 2);
vi prod(mxn);
void build(int v, int l, int r){
tl[v] = l;
tr[v] = r;
if(l == r){
tree[v] = state[l] * cont[l];
totcont[v] = cont[l];
}
else{
int mid = (l + r) / 2;
build(v * 2, l, mid);
build(v*2+1, mid+1, r);
tree[v] = tree[v*2] + tree[v*2+1];
tree[v] %= mod;
totcont[v] = totcont[v*2] + totcont[v*2+1];
totcont[v] %= mod;
}
}
vi la(mxn * 2);
void pull(int v){
tree[v] = tree[v*2] + tree[v*2+1];
tree[v] %= mod;
}
void toggle(int v){
la[v] = 1 - la[v];
tree[v] = totcont[v] - tree[v];
tree[v] %= mod;
if(tree[v] < 0){
tree[v] += mod;
}
}
void push(int v){
if(la[v]){
toggle(v*2);
toggle(v*2+1);
la[v] = 0;
}
}
void update(int v, int l, int r){
// cout<<"UPDATE "<<v<<'\n';
if(tl[v] > r || tr[v] < l){
return;
}
if(tl[v] >= l && tr[v] <= r){
// cout<<"INRANGW "<<v<<'\n';
// cout<<tree[v]<<'\n';
toggle(v);
// cout<<tree[v]<<'\n';
}
else{
push(v);
update(v*2, l, r);
update(v*2+1, l, r);
pull(v);
}
}
int dfs(int node, int from){
int p = chil[node];
for(auto u : adj[node]){
if(u != from && u < n){
p *= dfs(u, node);
p %= mod;
}
}
prod[node] = p;
return p;
}
void compcont(int node, int from, int cur){
if(node >= n){
cont[node - n] = cur;
return;
}
vi pref(chil[node]);
vi suf(chil[node]);
vi prods;
for(auto u : adj[node]){
if(u != from){
prods.pb(prod[u]);
}
}
// vout(prods);
pref[0] = prods[0];
FOR(i, 1, chil[node]){
pref[i] = pref[i-1] * prods[i];
pref[i] %= mod;
}
suf[chil[node] - 1] = prods.back();
for(int i = chil[node] - 2; i>=0; i--){
suf[i] = suf[i+1] * prods[i];
suf[i] %= mod;
}
// vout(pref);
// vout(suf);
int cnt = 0;
for(auto u : adj[node]){
if(u != from){
int cc = cur;
if(cnt != 0){
cc *= pref[cnt - 1];
cc %= mod;
}
if(cnt != suf.size() - 1){
cc *= suf[cnt + 1];
cc %= mod;
}
// cout<<cc<<'\n';
compcont(u, node, cc);
cnt++;
}
}
}
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
n = N; m = M; par = P; state = A;
adj.resize(n + m);
FOR(i, 1, n+m){
adj[P[i]].pb(i);
chil[P[i]]++;
}
dfs(0, -1);
for(int i = n; i<n+m; i++)prod[i] = 1;
// f0r(i,n+m)cout<<prod[i]<<' ';
// cout<<'\n';
compcont(0, -1, 1);
// f0r(i,m)cout<<cont[i]<<' ';
// cout<<'\n';
build(1, 0, m-1);
}
signed count_ways(signed l, signed r) {
l -= n; r -= n;
update(1, l, r);
return tree[1];
}
