Problem: You are given a binary array A=(A_1,A_2,\cdots,A_N) of length N.

Process Q queries of the following types. The i-th query is represented by three integers T_i,L_i,R_i.

* T_i=1: Replace the value of A_j with 1-A_j for each L_i \leq j \leq R_i.
* T_i=2: Calculate the inversion(*) of the array A_{L_i},A_{L_i+1},\cdots,A_{R_i}．



Note：The inversion of the array x_1,x_2,\cdots,x_k is the number of the pair of integers i,j with 1 \leq i < j \leq k, x_i > x_j.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 0 \leq A_i \leq 1
* 1 \leq Q \leq 2 \times 10^5
* 1 \leq T_i \leq 2
* 1 \leq L_i \leq R_i \leq N
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N Q
A_1 A_2 \cdots A_N
T_1 L_1 R_1
T_2 L_2 R_2
\vdots
T_Q L_Q R_Q


Output

For each query with T_i=2, print the answer.

Example

Input

5 5
0 1 0 0 1
2 1 5
1 3 4
2 2 5
1 1 3
2 1 2


Output

2
0
1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

struct RQ {
 struct RQV{ ULL n[2], x; };
 using RQRV = bool;
 static RQV Zero(){ return RQV{{0,0},0}; }
 static RQRV RZero(){ return false; }
 // addition
 static RQV f(RQV a,RQV b){
  return {
    {a.n[0]+b.n[0],a.n[1]+b.n[1]},
    a.x+b.x+a.n[1]*b.n[0]
  };
 }
 // update function
 static void uf(RQV& a,RQV b){ a = b; }
 // effect of range queries n-sized
 static void ef(RQV& a,RQRV b,int n){
  if(b){
   swap(a.n[0],a.n[1]);
   a.x = a.n[0]*a.n[1] - a.x;
  }
 }
 // range query update
 static void ruf(RQRV& a,RQRV b){ a = (a != b); }
 // comparation
 static bool cmp(RQV l,RQV r){ return false; }
 struct Node{
  RQV v; RQRV r;
 };
 int N;
 vector<Node> V;

 void init(int n){
  N=1; while (N<n) N*=2;
  V.assign(N*2,{Zero(),RZero()});
 }

 void spread(int i,int z){
  if (z!=1) {
   ef(V[i*2].v,V[i].r,z/2);
   ruf(V[i*2].r,V[i].r);
   ef(V[i*2+1].v,V[i].r,z/2);
   ruf(V[i*2+1].r,V[i].r);
  }
  V[i].r = RZero();
 }

 void upd(int p,RQV v){
  for(int d=N; d>=1; d/=2) spread(p/d,d);
  p+=N; uf(V[p].v,v);
  int z=1;
  while(p!=1){
   p/=2; z*=2;
   V[p].v = f(V[p*2].v,V[p*2+1].v);
   ef(V[p].v,V[p].r,z);
  }
 }

 void updr(int l,int r,RQRV v,int a=0,int b=0,int i=-1){
  if(i==-1){ a=0; b=N; i=1; }
  spread(i,b-a);
  if(r<=a || b<=l) return;
  if(l<=a && b<=r){
   ruf(V[i].r,v);
   ef(V[i].v,V[i].r,b-a);
   return;
  }
  updr(l,r,v,a,(a+b)/2,i*2);
  updr(l,r,v,(a+b)/2,b,i*2+1);
  V[i].v = f(V[i*2].v,V[i*2+1].v);
  ef(V[i].v,V[i].r,b-a);
 }

 RQV query(int l,int r,int a=0,int b=0,int i=-1){
  if(i==-1){ a=0; b=N; i=1; }
  if(r<=a || b<=l) return Zero();
  if(l<=a && b<=r) return V[i].v;
  RQV q1 = query(l,r,a,(a+b)/2,i*2);
  RQV q2 = query(l,r,(a+b)/2,b,i*2+1);
  q1 = f(q1,q2);
  ef(q1,V[i].r,min(r,b)-max(l,a));
  return q1;
 }

 int find(int l,RQV v,int a=0,int b=0,int i=-1){
  static RQV x;
  if(i==-1){ a=0; b=N; i=1; x=Zero(); }
  spread(i,b-a);
  if(b<=l) return N;
  if(l<=a && !cmp(v,f(x,V[i].v))){ x=f(x,V[i].v); return N; }
  if(b-a==1) return a;
  int q1 = find(l,v,a,(a+b)/2,i*2);
  if(q1!=N) return q1;
  return find(l,v,(a+b)/2,b,i*2+1);
 }
};

int N,Q;
RQ G;

int main(){
 scanf("%d%d",&N,&Q);
 G.init(N);
 rep(i,N){
  int a; scanf("%d",&a);
  if(a==0) G.upd(i,{{1,0},0});
  else G.upd(i,{{0,1},0});
 }
 rep(q,Q){
  int c; scanf("%d",&c);
  if(c==1){
   int l,r; scanf("%d%d",&l,&r); l--;
   G.updr(l,r,true);
  }
  if(c==2){
   int l,r; scanf("%d%d",&l,&r); l--;
   printf("%llu\n",G.query(l,r).x);
  }
 }
 
 return 0;
}