#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;
vector<vi>dp(mxn, vi(2));
vi dep(mxn);
vi cont(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 lef(mxn, -1);
vi rig(mxn, -1);
vi tl(mxn);
vi tr(mxn);
vi sts(mxn);
vi tree(mxn);
vi totcont(mxn);
int dfs(int node, int from){
int cur = 1;
int curtl = 1e9;
int curtr = -1;
for(auto u : adj[node]){
if(u != from){
if(lef[node] == -1)lef[node] = u;
else rig[node] = u;
dep[u] = 1 + dep[node];
cur += dfs(u, node);
curtl = min(curtl, tl[u]);
curtr = max(curtr, tr[u]);
}
}
if(node >= n){
cur = 0;
tl[node] = node - n;
tr[node] = node - n;
}
else{
tl[node] = curtl;
tr[node] = curtr;
}
sts[node] = cur;
return sts[node];
}
int dfs2(int node, int from){
int curcont = 0;
for(auto u : adj[node]){
if(u != from){
curcont += dfs2(u, node);
curcont %= mod;
// cout<<tree[u]<<" tree u "<<'\n';
totcont[node] += totcont[u];
totcont[node] %= mod;
}
}
if(sts[node] == 0){
tree[node] += state[node - n] * cont[node - n];
tree[node] %= mod;
totcont[node] = cont[node - n];
}
else{
tree[node] = curcont;
}
return tree[node];
}
vi la(mxn);
void pull(int v){
tree[v] = tree[lef[v]] + tree[rig[v]];
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(lef[v]);
toggle(rig[v]);
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(lef[v], l, r);
update(rig[v], l, r);
pull(v);
}
}
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);
}
dfs(0, -1);
f0r(i, m){
cont[i] = binexp(2, n - dep[i + n]);
}
dfs2(0, -1);
f0r(i, n+m){
// cout<<i<<' '<<tree[i]<<'\n';
}
// cout<< '\n';
f0r(i,n+m){
// cout<<tl[i]<<' '<<tr[i]<<'\n';
}
// cout<<'\n';
}
signed count_ways(signed l, signed r) {
l -= n; r -= n;
update(0, l, r);
f0r(i, n+m){
// cout<<tree[i]<<'\n';
}
// cout<< '\n';
return tree[0];
}
