#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> dp(300001);
vector<long long> bruh(300001);
vector<long long> br(300001);
vector<long long> f(300001);
long long p2[300001];
long long n,m;
const long long MOD = 1e9+2022;
void upd(long long l, long long r, long long x, long long nl, long long nr) {
if(l == nl && r == nr) {
f[x]++;
return;
}
long long m = (nl+nr)/2;
if(r <= m) {
upd(l,r,x*2+1,nl,m);
}
else if(l > m) {
upd(l,r,x*2+2,m+1,nr);
}
else {
upd(l,m,x*2+1,nl,m);
upd(m+1,r,x*2+2,m+1,nr);
}
long long a = dp[x*2+1],b = dp[x*2+2];
if(f[x*2+1]%2) {
a = (p2[br[x*2+1]]-a+MOD)%MOD;
}
if(f[x*2+2]%2) {
b = (p2[br[x*2+2]]-b+MOD)%MOD;
}
dp[x] = (p2[br[x*2+1]]*(a+b))%MOD;
}
void build(long long x) {
if(x >= n) {
dp[x] = bruh[x];
br[x] = 0;
return;
}
build(x*2+1);
build(x*2+2);
dp[x] = (p2[br[x*2+1]]*(dp[x*2+1]+dp[x*2+2]))%MOD;
br[x] = br[x*2+1]*2+1;
}
void init(int N, int M, vector<int> p, vector<int> a) {
p2[0] = 1;
for(int i = 1; i < 300001; i++) {
p2[i] = (p2[i-1]*2)%MOD;
}
n = N;
m = M;
for(int i = n; i < n+a.size(); i++) {
bruh[i] = a[i-n];
}
build(0);
}
int count_ways(int l, int r) {
upd(l-n,r-n,0,0,n);
return dp[0];
}
