#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define int long long
const int MXN = 2e5 + 5;
const int mod = 1e9 + 2022;
int n, m, res = 0;
vector<int> A, P;
vector<int> adj[MXN];
int dp[2][MXN], SZ[MXN];
int way[MXN];
void _init(int a)
{
if (adj[a].empty())
{
way[a] = 1;
return;
}
way[a] = adj[a].size();
for (int &v : adj[a])
{
_init(v);
way[a] = (way[a] * way[v]) % mod;
}
}
int val[MXN];
array<int, 2> st[MXN << 2];
int lz[MXN << 2];
void relax(int l, int r, int x)
{
if (!lz[x]) return;
swap(st[x][0], st[x][1]);
if (l == r)
{
lz[x] = 0;
return;
}
lz[2*x] ^= lz[x], lz[2*x + 1] ^= lz[x];
lz[x] = 0;
}
void upd(int l, int r, int x, int lx, int rx)
{
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
lz[x] ^= 1;
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx);
upd(mid + 1, r, 2*x + 1, lx, rx);
st[x][0] = (st[2*x][0] + st[2*x + 1][0]) % mod;
st[x][1] = (st[2*x][1] + st[2*x + 1][1]) % mod;
}
void build(int l, int r, int x)
{
if (l == r)
{
st[x][0] = A[l] * val[l];
st[x][1] = (A[l] ^ 1) * val[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st[x][0] = (st[2*x][0] + st[2*x + 1][0]) % mod;
st[x][1] = (st[2*x][1] + st[2*x + 1][1]) % mod;
}
void init(int32_t N, int32_t M, vector<int32_t> PP, vector<int32_t> AA)
{
n = N, m = M;
for (int32_t &i : PP) P.push_back(i);
for (int32_t &i : AA) A.push_back(i);
reverse(A.begin(), A.end());
A.resize(N + M, 0);
reverse(A.begin(), A.end());
for (int i = 1; i < N + M; i++) adj[P[i]].push_back(i);
_init(0);
for (int i = N; i < N + M; i++)
{
int x = i;
val[i] = 1;
while (P[x] != -1)
{
for (int &v : adj[P[x]])
{
if (v == x) continue;
val[i] = (val[i] * way[v]) % mod;
}
x = P[x];
}
}
build(N, N + M - 1, 1);
}
int32_t count_ways(int32_t L, int32_t R) {
upd(n, n + m - 1, 1, L, R);
return st[1][0];
}
