#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 69;
const int mod = 1e9 + 2022;
vector <int> adj[N];
int n, m;
int w1[N], tot[N], ok[N], aa[N];
int power(int x, int y){
if (y==0) return 1;
int v = power(x, y/2);
v *= v; v %= mod;
if (y & 1) return v * x % mod;
else return v;
}
void dfs(int u){
int cnt = 0;
for (int v : adj[u]){
dfs(v);
cnt++;
}
if (u >= n) return;
int curr = 1;
w1[u] = 0;
for (int v : adj[u]){
ok[v] = curr;
curr *= tot[v];
curr %= mod;
}
tot[u] = curr * cnt % mod;
curr = 1;
for (int i = adj[u].size() - 1; i >= 0; i--){
int v = adj[u][i];
ok[v] *= curr;
ok[v] %= mod;
curr *= tot[v];
curr %= mod;
}
for (int v : adj[u]){
w1[u] += w1[v] * ok[v] % mod;
w1[u] %= mod;
}
}
void init(int32_t N, int32_t M, vector<int32_t> p, vector<int32_t> a) {
n = N;
m = M;
for (int i = 1; i < n + m; i++){
adj[p[i]].push_back(i);
}
for (int i = n; i < n + m; i++){
for (int j = n; j < n + m; j++){
tot[j] = 1;
if (j == i) w1[j] = 1;
else w1[j] = 0;
}
dfs(0);
aa[i] = w1[0];
}
for (int i = 0; i < m; i++){
if (a[i] == 1)
w1[i + n] = 1;
else w1[i + n] = 0;
tot[i + n] = 1;
}
}
int32_t count_ways(int32_t l, int32_t r) {
for (int i = l; i <= r; i++){
w1[i] ^= 1;
}
int32_t ans = 0;
for (int i = n; i < n + m; i++){
if (w1[i]) ans += aa[i], ans %= mod;
}
return ans;
}
// int32_t main(){
// int32_t n, m; cin >> n >> m;
// vector <int32_t> p(n + m), a(m);
// for (auto &x : p) cin >> x;
// for (auto &x : a) cin >> x;
// init(n, m, p, a);
// int q; cin >> q;
// while(q--){
// int32_t l, r;
// cin >> l >> r;
// cout << count_ways(l, r) << "\n";
// }
// return 0;
// }
