#include "circuit.h"
#include <vector>
#include <iostream>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define sz(x) (ll)x.size()
#define endl "\n"
typedef vector <int> vi;
typedef pair <ll, ll> ii;
typedef vector <ii> vii;
#define MOD 1000002022
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
void printVct(vi &v){
for (ll i =0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
ll mpow(ll a, ll b){
if (b == 0) return 1;
if (b % 2) return (a * (mpow((a*a)%MOD, b/2)% MOD)) % MOD;
return mpow((a*a)%MOD, b/2)%MOD;
}
#define MID ((l+r)/2)
ll n,m;
vi p,a;
ll dif, ans;
struct node{ //sum seg tree with lazy (base = input gates => base size = m)
node *L, *R;
ll val;
ll lazy; //0 or 1 => 1 means toggled
void build (ll l = 0, ll r=m-1){
lazy = 0;
if (l == r){
val = a[l];
}
else{
L = new node, R =new node;
L->build(l, MID), R->build(MID+1,r);
val = L->val + R->val;
}
}
ll query(ll tl, ll tr, ll l = 0, ll r =m-1){
if (tl <= l && r <= tr){
return val;
}
else if (r < tl || l > tr){
return 0;
}
else{
propagate(l,r);
return L->query(tl,tr,l,MID) + R->query(tl,tr,MID+1,r);
}
}
void update(ll tl, ll tr, ll l = 0, ll r =m-1){
if (tl <= l && r <= tr){
ll siz = r-l+1;
val = siz - val; //all toggled
lazy = !lazy;
}
else if (r < tl || l > tr){
return;
}
else{
propagate(l,r);
L->update(tl,tr,l,MID);
R->update(tl,tr,MID+1,r);
val = L->val + R->val;
}
}
void propagate(ll l, ll r){
if (lazy){
ll sizL = MID-l+1;
ll sizR = r-(MID+1)+1;
L->val = sizL - (L->val);
R->val = sizR - (R->val);
L->lazy = !(L->lazy);
R->lazy = !(R->lazy);
lazy = 0;
}
}
};
node root;
void init(int N, int M, vector <int> P, vector<int> A) {
n= N, m = M;
p = P;
a = A;
//subtask 4,5:
ll treeHeight = 0;
ll p = m;
while (p){
p/=2;
treeHeight++;
}
// dbg(treeHeight);
dif = 1;
ll p2 = 1;
// dbg(m-1-treeHeight);
for (ll i = 0; i<=m-1-treeHeight; i++){
dif = (dif + p2) % MOD;
p2 = (p2 * 2) % MOD;
}
// dbg(dif);
//calc ans:
ll curOff = 0;
for (ll i = 0; i<m; i++){
if (!a[i]) curOff++;
}
ll all = mpow(2, n);
ans = (all - ((dif * curOff) % MOD) + MOD) % MOD;
// dbg(ans);
//seg tree for sub 5:
root.build();
}
int count_ways(int L, int R) {
//subtask 4: L = R
ll l = L-n, r = R-n;
ll prevOn = root.val;
root.update(l,r);
ll curOn = root.val;
ll difVal = (((curOn - prevOn + MOD) % MOD) * dif) % MOD;
ans = (ans + difVal) % MOD;
return ans;
}
/*
3 4 4
-1 0 0 1 1 2 2
1 1 1 1
4 4
4 4
4 5
4 4
7 8 1
-1 0 0 1 1 2 2 3 3 4 4 5 5 6 6
1 1 1 1 1 1 1 1
10 10
*/
/*
subtask 1:
ll l = L-n, r = R-n;
ll curOn = 0;
for (ll i =0; i<m; i++){
if (i >= l && i <= r){
a[i] = !a[i];
}
if (a[i]) curOn++;
}
*/
