#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;
const ll mod=1e9+2022;
const ll N=2e5+9;
ll n, m, a[N], pw[N], cnt[N], ps[N], seg[N*4], lazy[N*4], ans=0;
vector<ll> v[N], pre[N], suf[N];
void dfs(ll x){
if (x>=n){
pw[x]=1;
return;
}
pw[x]=v[x].size();
for (ll i: v[x]){
dfs(i);
pw[x]=pw[x]*pw[i]%mod;
}
}
void dfs2(ll x, ll now=1){
if (x>=n){
cnt[x-n+1]=ps[x-n+1]=now;
return;
}
ll sz=v[x].size();
pre[x].resize(sz);
pre[x][0]=pw[v[x][0]];
for (int i=1; i<sz; i++) pre[x][i]=pre[x][i-1]*pw[v[x][i]]%mod;
suf[x].resize(sz);
suf[x][sz-1]=pw[v[x][sz-1]];
for (int i=sz-2; i>=0; i--) suf[x][i]=suf[x][i+1]*pw[v[x][i]]%mod;
for (int i=0; i<sz; i++){
ll tmp=now;
if (i) tmp=tmp*pre[x][i-1]%mod;
if (i<sz-1) tmp=tmp*suf[x][i+1]%mod;
dfs2(v[x][i], tmp);
}
}
void push(ll id, ll x, ll y){
if (!lazy[id]) return;
lazy[id]=0;
seg[id]=((ps[y]-ps[x-1]-seg[id])%mod+mod)%mod;
if (x!=y){
lazy[id*2]^=1;
lazy[id*2+1]^=1;
}
}
void build(ll id=1, ll x=1, ll y=m){
if (x==y){
seg[id]=cnt[x]*a[x];
lazy[id]=0;
return;
}
ll mid=(x+y)/2;
build(id*2, x, mid);
build(id*2+1, mid+1, y);
seg[id]=(seg[id*2]+seg[id*2+1])%mod;
}
void update(ll l, ll r, ll id=1, ll x=1, ll y=m){
push(id, x, y);
if (l<=x && y<=r){
lazy[id]^=1;
push(id, x, y);
return;
}
if (l>y || r<x) return;
ll mid=(x+y)/2;
update(l, r, id*2, x, mid);
update(l, r, id*2+1, mid+1, y);
seg[id]=(seg[id*2]+seg[id*2+1])%mod;
}
ll qry(ll p, ll id=1, ll x=1, ll y=m){
push(id, x, y);
if (x==y) return seg[id];
ll mid=(x+y)/2;
if (p<=mid) return qry(p, id*2, x, mid);
return qry(p, id*2+1, mid+1, y);
}
void init(int N, int M, vector<int> P, vector<int> A){
n=N, m=M;
for (int i=1; i<n+m; i++) v[P[i]].push_back(i);
for (int i=0; i<m; i++) a[i+1]=A[i];
dfs(0);
dfs2(0);
for (int i=2; i<=m; i++) ps[i]=(ps[i]+ps[i-1])%mod;
build();
}
int count_ways(int L, int R){
update(L-n+1, R-n+1);
push(1, 1, m);
return seg[1];
}
