#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
long long n,m;
vector<long long> haha[300001];
vector<long long> prod(300001);
vector<long long> wow(300001,1);
vector<long long> no(300001);
vector<long long> sum(800001);
vector<long long> idk(800001);
vector<long long> val(800001);
const long long MOD = 1e9+2022;
void build(long long l, long long r, long long x) {
if(l == r) {
sum[x] = wow[l+n];
if(no[l]) {
val[x] = sum[x];
}
else {
val[x] = 0;
}
idk[x] = 0;
return;
}
long long mid = (l+r)/2;
build(l,mid,x*2+1);
build(mid+1,r,x*2+2);
sum[x] = (sum[x*2+1]+sum[x*2+2])%MOD;
val[x] = (val[x*2+1]+val[x*2+2])%MOD;
}
void upd(long long l, long long r, long long ql, long long qr, long long x) {
if(l == ql && r == qr) {
idk[x]++;
idk[x]%=2;
val[x] = (sum[x]-val[x]+MOD)%MOD;
return;
}
long long mid = (l+r)/2;
if(qr <= mid) {
upd(l,mid,ql,qr,x*2+1);
}
else if(ql >= mid+1) {
upd(mid+1,r,ql,qr,x*2+2);
}
else {
upd(l,mid,ql,mid,x*2+1);
upd(mid+1,r,mid+1,qr,x*2+2);
}
val[x] = (val[x*2+1]+val[x*2+2])%MOD;
if(idk[x]%2) {
val[x] = (sum[x]-val[x]+MOD)%MOD;
}
}
void dfs(long long a) {
long long sb = max(1LL,(long long)haha[a].size());
for(long long v: haha[a]) {
dfs(v);
sb*=prod[v];
sb%=MOD;
}
prod[a] = sb;
}
void dude(long long a) {
vector<long long> pr(haha[a].size()+1,1);
vector<long long> su(haha[a].size()+1,1);
for(int i = 0; i < haha[a].size(); i++) {
pr[i+1] = prod[haha[a][i]];
su[i] = prod[haha[a][i]];
}
for(int i = 1; i <= haha[a].size(); i++) {
pr[i]*=pr[i-1];
pr[i]%=MOD;
}
for(int i = haha[a].size()-1; i >= 0; i--) {
su[i]*=su[i+1];
su[i]%=MOD;
}
for(int i = 0; i < haha[a].size(); i++) {
wow[haha[a][i]] = (((wow[a]*pr[i])%MOD)*su[i+1])%MOD;
dude(haha[a][i]);
}
}
void init(int N, int M, vector<int> p, vector<int> a) {
n = N;
m = M;
for(long long i = 1; i < n+m; i++) {
haha[p[i]].push_back(i);
}
dfs(0);
dude(0);
for(int i = 0; i < a.size(); i++) {
no[i] = a[i];
}
build(0,m-1,0);
}
int count_ways(int l, int r) {
upd(0,m-1,l-n,r-n,0);
return val[0];
}
