#include <bits/stdc++.h>
using namespace std;
namespace {
int N, M;
vector<vector<int>> adj;
// vector<int> A;
using int64 = long long;
const int md = 1000002022;
class lazy_segment_tree {
struct node {
int zc, oc;
node operator+(const node &r) const { return {zc + r.zc, oc + r.oc}; }
};
int n;
vector<node> seg;
vector<int> lazy;
void build(int v, int tl, int tr) {
if (tl == tr) {
seg[v] = {1, 0};
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm), build(2 * v + 1, tm + 1, tr);
seg[v] = seg[2 * v] + seg[2 * v + 1];
}
void push(int v) {
if (lazy[v]) {
swap(seg[v].zc, seg[v].oc);
}
if (v < 2 * n) {
lazy[2 * v] ^= lazy[v];
lazy[2 * v + 1] ^= lazy[v];
}
lazy[v] = 0;
}
void pull(int v) {
seg[v] = seg[2 * v] + seg[2 * v + 1];
}
void toggle(int v, int tl, int tr, int l, int r) {
push(v);
if (r < tl || tr < l) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] ^= 1;
push(v);
return;
}
int tm = (tl + tr) / 2;
toggle(2 * v, tl, tm, l, r), toggle(2 * v + 1, tm + 1, tr, l, r);
pull(v);
}
public:
lazy_segment_tree() {}
lazy_segment_tree(int n) : n(n), seg(4 * n), lazy(8 * n) {
build(1, 0, n - 1);
}
void toggle(int l, int r) {
toggle(1, 0, n - 1, l, r);
}
int64 query() { return seg[1].oc; }
};
int64 binexp(int64 a, int b) {
int64 ans = 1, v = a;
while (b) {
if (b & 1) {
ans = (ans * v) % md;
}
b >>= 1;
v = (v * v) % md;
}
return ans;
}
lazy_segment_tree st;
} // namespace
void init(int N, int M, vector<int> P, vector<int> A) {
::N = N, ::M = M;
adj.resize(N + M + 1);
for (int i = 1; i < N + M; ++i) {
adj[P[i]].push_back(i);
}
// ::A = A;
st = lazy_segment_tree(M);
for (int i = 0; i < M; ++i) {
if (A[i]) {
st.toggle(i, i);
}
}
}
int count_ways(int L, int R) {
// for (int i = L; i <= R; ++i) {
// A[i - N] = 1 - A[i - N];
// }
st.toggle(L - N, R - N);
return (binexp(2, N - bit_width(unsigned(M)) + 1) * st.query()) % md;
}
#ifdef MACOS_LOCAL
#include "stub.cpp"
#endif
