#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
const int MOD = 1e9 + 2022;
inline int add(int x, int y) {
x += y;
if (x >= MOD)
return x - MOD;
if (x < 0)
return x + MOD;
return x;
}
inline int mul(int x, int y) {
return (long long)x * y % MOD;
}
struct Node {
int tot, sum, lazy;
Node(int tot, int sum, int lazy) : tot(tot), sum(sum), lazy(lazy) {}
Node() : tot(0), sum(0), lazy(0) {}
};
class Tournament {
int m, offset;
vector <Node> tour;
public:
Node merge(Node lhs, Node rhs) {
return Node(add(lhs.tot, rhs.tot), add(lhs.sum, rhs.sum), 0);
}
void refresh(int x) {
tour[x] = merge(tour[2 * x], tour[2 * x + 1]);
}
Tournament(int m, int n, vector <int> v, vector <int> s) : m(m) {
for (offset = 1; offset < n; offset *= 2);
tour.resize(2 * offset);
for (int i = 0; i < n; i++)
tour[i + offset] = Node(v[i], s[i] * v[i], 0);
for (int i = offset - 1; i; i--)
refresh(i);
}
Tournament() {}
void prop(int x) {
if (!tour[x].lazy)
return;
tour[x].sum = add(tour[x].tot, -tour[x].sum);
if (x < offset) {
tour[2 * x].lazy ^= 1;
tour[2 * x + 1].lazy ^= 1;
}
tour[x].lazy = 0;
}
void update(int x, int lo, int hi, int from, int to) {
prop(x);
if (lo >= to || hi <= from)
return;
if (lo >= from && hi <= to) {
tour[x].lazy ^= 1;
prop(x);
return;
}
int mid = (lo + hi) / 2;
update(2 * x, lo, mid, from, to);
update(2 * x + 1, mid, hi, from, to);
refresh(x);
}
void update(int from, int to) {
update(1, 0, offset, from - m, to - m);
}
int query() {
prop(1);
return tour[1].sum;
}
};
Tournament solver;
void init(int N, int M, vector <int> p, vector <int> a) {
vector <int> pos(N + M);
vector <vector <int>> ch(N);
for (int i = 1; i < N + M; i++) {
pos[i] = ch[p[i]].size();
ch[p[i]].push_back(i);
}
vector <int> sz(N), sub(N + M, 1);
for (int i = 0; i < N; i++)
sz[i] = sub[i] = ch[i].size();
for (int i = N - 1; i; i--)
sub[p[i]] = mul(sub[p[i]], sub[i]);
vector <vector <int>> pref(N), suff(N);
for (int i = 0; i < N; i++) {
pref[i].resize(sz[i]);
suff[i].resize(sz[i]);
for (int j = 0; j < sz[i]; j++)
pref[i][j] = mul(j ? pref[i][j - 1] : 1, sub[ch[i][j]]);
for (int j = sz[i] - 1; j >= 0; j--)
suff[i][j] = mul(j < sz[i] - 1 ? suff[i][j + 1] : 1, sub[ch[i][j]]);
}
vector <int> prod(N + M);
prod[0] = 1;
for (int i = 1; i < N + M; i++)
prod[i] = mul(prod[p[i]], mul(pos[i] ? pref[p[i]][pos[i] - 1] : 1, pos[i] < sz[p[i]] - 1 ? suff[p[i]][pos[i] + 1] : 1));
solver = Tournament(N, M, vector <int> (prod.begin() + N, prod.end()), a);
}
int count_ways(int l, int r) {
solver.update(l, r + 1);
return solver.query();
}
