#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)x.size()
#define ar array
#include "circuit.h"
using namespace std;
const int mod = int(1e9) + 2022;
void fadd(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
}
int add(int x, int y) {
return x+y >= mod ? x+y-mod : x+y;
}
struct seg {
int N; vector<int> tree, tot, lazy;
seg() {}
seg(int n, const vector<int>& v, const vector<int>& a) : N(1<<(__lg(n)+1)), tree(2*N), tot(2*N), lazy(2*N) {
for (int i = 0; i < n; i++) tot[i+N] = v[i], tree[i+N] = v[i] * a[i];
for (int i = N-1; i >= 1; i--) tot[i] = add(tot[i*2], tot[i*2+1]), tree[i] = add(tree[i*2], tree[i*2+1]);
}
void push(int node) {
if (!lazy[node]) return;
tree[node] = tot[node] - tree[node];
if (tree[node] < 0) tree[node] += mod;
if (node < N) {
lazy[node*2] ^= 1;
lazy[node*2+1] ^= 1;
}
lazy[node] = 0;
}
void update(int node, int nl, int nr, int ql, int qr) {
push(node);
if (ql > nr || qr < nl) return;
if (ql <= nl && nr <= qr) {
lazy[node] ^= 1; push(node); return;
}
int mid = (nl+nr)/2;
update(node*2, nl, mid, ql, qr);
update(node*2+1, mid+1, nr, ql, qr);
tree[node] = add(tree[node*2], tree[node*2+1]);
}
} st;
vector<int> p, a, sub, sub2, val;
vector<vector<int>> adj;
int n, m;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N, m = M;
p = P, a = A;
adj.resize(N), sub.resize(N+M, 1), sub2.resize(N+M, 1);
for (int i = 1; i < N + M; i++) adj[P[i]].emplace_back(i);
for (int i = N-1; i >= 0; i--) {
sub[i] = sz(adj[i]);
int cur = sz(adj[i]);
vector<int> pref(cur), suff(cur);
for (int j = 0; j < cur; j++) {
pref[j] = suff[j] = sub[adj[i][j]];
}
for (int j = 1; j < cur; j++) pref[j] = (ll)pref[j-1] * pref[j] % mod;
for (int j = cur-2; j >= 0; j--) suff[j] = (ll)suff[j+1] * suff[j] % mod;
for (int j = 0; j < cur; j++) {
int u = adj[i][j];
sub[i] = (ll)sub[i] * sub[u] % mod;
sub2[u] = (ll)(j ? pref[j-1] : 1) * (j+1 < cur ? suff[j+1] : 1) % mod;
}
}
val.resize(N+M);
val[0] = 1;
for (int i = 1; i < N + M; i++) val[i] = (ll)val[p[i]] * sub2[i] % mod;
vector<int> val2(M);
for (int i = N; i < N+M; i++) val2[i-N] = val[i];
st = seg(m, val2, A);
}
int count_ways(int L, int R) {
st.update(1, 0, st.N-1, L - n, R - n);
return st.tree[1];
}
