#include <bits/stdc++.h>
#include "circuit.h"
typedef long long int64;
using namespace std;
const int64 mod = 1000002022;
const int maxn = 2e5 + 2;
vector <int> ad [maxn];
int64 depth[maxn];
int64 dp[4 * maxn]; // each node contributes 2^(N - depth)
int64 pref[4 * maxn];
int64 lazy[4 * maxn];
int64 pw [maxn];
int n,m;
void dfs (int x) {
for (int v: ad[x]) {
depth[v] = depth[x] + 1;
dfs(v);
}
}
int64 sum (int l, int r) {
return (pref[r] - pref[l - 1] + mod) % mod;
}
void push (int x, int l, int r) {
if (!lazy[x]) return;
int mid = (l + r) / 2;
dp[x * 2 + 1] = (sum(l, mid) - dp[x * 2 + 1] + mod) % mod;
dp[x * 2 + 2] = (sum(mid + 1, r) - dp[x * 2 + 2] + mod) % mod;
lazy[x * 2 + 1] = !lazy[x * 2 + 1];
lazy[x * 2 + 2] = !lazy[x * 2 + 2];
lazy[x] = 0;
}
void upd (int x, int l, int r, int il, int ir) {
// cout << x << " " << l << " " << r << " " << il << " " << ir << "\n";
if (il <= l && r <= ir) {
// cout << l << " " << r << " " << sum(l, r) << "\n";
dp[x] = (sum(l, r) - dp[x] + mod) % mod;
lazy[x] = !lazy[x];
return;
}
if (l > ir || r < il) return;
push(x, l, r);
int mid = (l + r) / 2;
upd(x * 2 + 1, l, mid, il, ir);
upd(x * 2 + 2, mid + 1, r, il, ir);
dp[x] = (dp[x * 2 + 1] + dp[x * 2 + 2]) % mod;
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N, m = M;
pw[0] = 1;
for (int i = 1; i < maxn; i++){
pw[i] = pw[i-1] * 2 % mod;
}
for (int i = 1; i < N + M; i++){
ad[P[i]].push_back(i);
}
dfs(0);
for (int i = 0; i < M; i++){
pref[i] = ((i ? pref[i-1]: 0) + pw[N - depth[i + N]] )% mod;
}
for (int i = 0; i < M; i++){
if (A[i]) upd(0, 0, M - 1, i, i);
}
}
int count_ways(int L, int R) {
upd(0, 0, m - 1, L - n, R - n);
return dp[0];
}
