#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1000000000+2022;
const int LIM=2e5+7;
vector<int>V[LIM];
ll ilo[LIM], tr[4*LIM], sum[4*LIM], lazy[4*LIM], N=1;
void DFS(int x) {
ilo[x]=max(1, (int)V[x].size());
for(auto i : V[x]) {
DFS(i);
ilo[x]=(ilo[x]*ilo[i])%MOD;
}
}
void DFS2(int x, ll akt) {
if(!V[x].size()) {
sum[N+x]=akt;
return;
}
vector<ll>pref(V[x].size()), suf(V[x].size());
rep(i, V[x].size()) {
pref[i]=ilo[V[x][i]];
suf[V[x].size()-i-1]=ilo[V[x][V[x].size()-i-1]];
if(i) {
pref[i]=(pref[i]*pref[i-1])%MOD;
suf[V[x].size()-i-1]=(suf[V[x].size()-i-1]*suf[V[x].size()-i])%MOD;
}
}
rep(i, V[x].size()) {
ll p=akt;
if(i) p=(p*pref[i-1])%MOD;
if(i+1<V[x].size()) p=(p*suf[i+1])%MOD;
DFS2(V[x][i], p);
}
}
void init(int n, int m, vector<int> P, vector<int> A) {
while(N<n+m) N*=2;
for(int i=1; i<P.size(); ++i) V[P[i]].pb(i);
DFS(0);
DFS2(0, 1);
rep(i, m) if(A[i]) tr[N+n+i]=sum[N+n+i];
for(int i=N-1; i; --i) {
tr[i]=(tr[2*i]+tr[2*i+1])%MOD;
sum[i]=(sum[2*i]+sum[2*i+1])%MOD;
}
}
void spl(int v) {
tr[2*v]=(sum[2*v]-tr[2*v]+MOD)%MOD;
tr[2*v+1]=(sum[2*v+1]-tr[2*v+1]+MOD)%MOD;
lazy[2*v]^=1;
lazy[2*v+1]^=1;
lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b) {
if(r<a || l>b) return;
if(a<=l && r<=b) {
tr[v]=(sum[v]-tr[v]+MOD)%MOD;
lazy[v]^=1;
return;
}
if(lazy[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b);
upd(2*v+1, mid+1, r, a, b);
tr[v]=(tr[2*v]+tr[2*v+1])%MOD;
}
int count_ways(int l, int r) {
upd(1, 0, N-1, l, r);
return tr[1];
}
