#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 2022;
vector<long long> coeff;
class segtree {
public:
vector<long long> sums, ori;
vector<bool> toggle;
int n;
segtree() {
}
void build(vector<long long>& a, int ll, int rr, int v) {
if (rr - ll == 1) {
sums[v] = a[ll];
return;
}
int m = (ll + rr) >> 1;
build(a, ll, m, 2 * v + 1);
build(a, m, rr, 2 * v + 2);
sums[v] = (sums[2 * v + 1] + sums[2 * v + 2]) % M;
}
void build(vector<long long> a) {
n = a.size();
sums.resize(4 * n);
toggle.resize(4 * n);
build(a, 0, n, 0);
ori = sums;
}
void modify(int l, int r, int ll, int rr, int v) {
if (ll >= r || l >= rr) {
return;
}
if (ll >= l && rr <= r) {
sums[v] = (ori[v] - sums[v]) % M;
toggle[v] = toggle[v] ^ 1;
return;
}
int m = (ll + rr) >> 1;
if (toggle[v]) {
toggle[v] = 0;
toggle[2 * v + 1] = toggle[2 * v + 1] ^ 1;
sums[2 * v + 1] = (ori[2 * v + 1] - sums[2 * v + 1]) % M;
toggle[2 * v + 2] = toggle[2 * v + 2] ^ 1;
sums[2 * v + 2] = (ori[2 * v + 2] - sums[2 * v + 2]) % M;
}
modify(l, r, ll, m, 2 * v + 1);
modify(l, r, m, rr, 2 * v + 2);
sums[v] = (sums[2 * v + 1] + sums[2 * v + 2]) % M;
}
void modify(int l, int r) {
modify(l, r, 0, n, 0);
}
};
int nn, mm;
segtree seg;
void init(int n, int m, vector<int> p, vector<int> a) {
nn = n;
mm = m;
coeff.resize(n + m);
vector<vector<int>> g(n + m);
for (int i = 1; i < n + m; i++) {
g[p[i]].push_back(i);
}
vector<long long> sub(n + m, 1);
auto Sub = [&](auto&& self, int v) -> void {
if (g[v].size() != 0) {
sub[v] = g[v].size();
}
for (int u : g[v]) {
self(self, u);
sub[v] *= sub[u];
sub[v] %= M;
}
};
Sub(Sub, 0);
auto Dfs = [&](auto&& self, int v, long long prod) -> void {
if (n <= v) {
coeff[v] = prod;
} else {
vector<long long> pref(g[v].size() + 1, 1), suff(g[v].size() + 1, 1);
for (int i = 1; i <= g[v].size(); i++) {
if (g[g[v][i - 1]].empty()) {
pref[i] = pref[i - 1];
continue;
}
pref[i] = pref[i - 1] * sub[g[v][i - 1]];
pref[i] %= M;
}
for (int i = g[v].size() - 1; i >= 0; i--) {
if (g[g[v][i]].empty()) {
suff[i] = suff[i + 1];
continue;
}
suff[i] = suff[i + 1] * sub[g[v][i]];
suff[i] %= M;
}
for (int k = 0; k < g[v].size(); k++) {
self(self, g[v][k], (((static_cast<long long>(prod) * static_cast<long long>(pref[k])) % M) * static_cast<long long>(suff[k + 1])) % M);
}
}
};
Dfs(Dfs, 0, 1);
vector<long long> small(m);
for (int i = 0; i < m; i++) {
small[i] = coeff[i + n];
}
seg.build(small);
for (int i = 0; i < m; i++) {
if (!a[i]) {
seg.modify(i, i + 1);
}
}
}
int count_ways(int l, int r) {
seg.modify(l - nn, r - nn + 1);
return seg.sums[0];
}
