#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 8e5 + 1;
int A[MAXN];
vector<int> adj[MAXN];
int N, M;
array<ll, 2> dp[MAXN];
int lazy[MAXN];
void mrg(int i) {
int j = i * 2 + 1;
int k = i * 2 + 2;
ll now = dp[j][0] * dp[k][1] % MOD;
now = (now + (dp[j][1] * dp[k][0]) % MOD) % MOD;
dp[i][1] = now;
dp[i][0] = now;
now = (2LL * dp[j][0] * dp[k][0]) % MOD;
dp[i][0] = (dp[i][0] + now) % MOD;
now = (2LL * dp[j][1] * dp[k][1]) % MOD;
dp[i][1] = (dp[i][1] + now) % MOD;
cout << i << " " << dp[i][1] << " " << dp[i][0] << "\n";
}
void upd(int i) {
if (lazy[i] == 0) return;
lazy[i * 2 + 1] ^= lazy[i];
lazy[i * 2 + 2] ^= lazy[i];
lazy[i] = 0;
swap(dp[i][0], dp[i][1]);
}
void update(int i, int l, int r, int ql, int qr) {
if (ql > r || l > qr) return;
cout << l << " " << r << "\n";
if (ql <= l && r <= qr) {
lazy[i] ^= 1;
upd(i);
return;
}
int m = (l + r) / 2;
update(i * 2 + 1, l, m, ql, qr);
update(i * 2 + 2, m + 1, r, ql, qr);
mrg(i);
}
void init(int _N, int _M, std::vector<int> P, std::vector<int> _A) {
N = _N;
M = _M;
for (int i = N; i < N + M; ++i) {
A[i] = _A[i - N];
}
for (int i = 1; i < N + M; ++i) {
adj[P[i]].push_back(i);
}
auto dfs = [&](auto& dfs, int i) -> void {
if (i >= N) {
// cout << i << " " << A[i] << "\n";
dp[i][A[i]] = 1;
dp[i][1 ^ A[i]] = 0;
return;
}
dfs(dfs, i * 2 + 1);
dfs(dfs, i * 2 + 2);
mrg(i);
};
dfs(dfs, 0);
}
int count_ways(int L, int R) {
// cout << dp[1][1] << " -> ";
update(0, 0, M - 1, L - N, R - N);
return dp[0][1];
}
