#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
struct event{
int l,r,id;
};
int row1[MAXN];
int row[3*MAXN];
int n,q;
vector<event> queries[MAXN];
int a[MAXN],ans[MAXN];
int answer(int l,int r){
int res=0;
for(int i=l;i<=r;i++)res+=a[i];
return res;
}
void calc_queries(int w){
for(auto s:queries[w]){
ans[s.id]=answer(s.l,s.r);
}
}
vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R){
n=int(X.size());
q=int(T.size());
for(int i=0;i<q;i++){
queries[T[i]].push_back({L[i],R[i],i});
}
for(int i=0;i<n;i++)a[i]=X[i];
calc_queries(0);
row1[0]=Y[1];
for(int i=1;i<n;i++){
if(row1[i-1]==0 and X[i]==0)row1[i]=1;
else row1[i]=0;
}
/// here we have row 1
for(int i=0;i<n;i++)a[i]=row1[i];
calc_queries(1);
int start=2*n+1,fr=start;
row[start-1]=Y[2];
for(int i=start;i<=start+n-2;i++){
if(row[i-1]==0 and row1[i-start+1]==0)row[i]=1;
else row[i]=0;
}
for(int i=start;i<=start+n-1;i++){
if(row[i]==1){
fr=i; break;
}
}
/// here we have row 2
for(int i=0;i<n;i++)a[i]=row[i+start-1];
calc_queries(2);
for(int i=3;i<n;i++){
start--;
row[start-1]=Y[i];
for(int f=start;f<fr-1;f++){
row[f]=1-row[f-1];
}
for(int f=start;f<=fr;f++){
if(row[f]==1){
fr=f; break;
}
}
for(auto s:queries[i]){
for(int f=s.l;f<=s.r;f++){
ans[s.id]+=row[f+start-1];
}
}
}
vector<long long> sol;
for(int i=0;i<q;i++){
sol.push_back(ans[i]);
}
return sol;
}
/*int main(){
//mosaic({1,1,1,0,0,0,1,1,0,1,0,1,1,1,0},{1,1,1,0,0,0,1,1,0,1,0,1,1,1,0},{},{},{},{});
auto yo=mosaic({1, 0, 1, 0}, {1, 1, 0, 1}, {1, 3}, {1, 3}, {0, 0}, {3, 3});
for(auto s:yo)cout<<s<<" ";
return 0;
}*/
