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 <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;


typedef array<ll, 3> ar;
template <typename T, typename E>
struct SegmentTree{
  vector<T> dat;vector<E> laz;
  typedef function<T(T, T)> F;//merge
  typedef function<T(T, E)> G;//dat lazy
  typedef function<E(E, E)> H;//lazy lazy
  typedef function<E(E, int)> P;//lazy len
  int n;F f;G g;H h;
  T d1;//datの零元
  E d0;//lazyの零元
  P p;

  SegmentTree(int m,F f,G g,H h,T d1,E d0,
  	      vector<T> v=vector<T>(),P p=[](E a,int b){return a;}):
      f(f),g(g),h(h),d1(d1),d0(d0),p(p){
      init(m);
      if(m==(int)v.size()) build(m,v);
  }
  void init(int m){
    n = 1;
    while(n<m) n*=2;
    dat.clear();laz.clear();
    dat.resize(2*n-1);laz.resize(2*n-1);
  }
  void build(int m, vector<T> v){
    for(int i=0;i<m;i++) dat[i+n-1] = v[i];
    for(int i=n-2;i>=0;i--) dat[i] = f(dat[i*2+1], dat[i*2+2]);
  }
  inline void eval(int len, int k){
    if(laz[k]==d0) return;
    if(k*2+1<n*2-1){
      laz[k*2+1]=h(laz[k*2+1], laz[k]);
      laz[k*2+2]=h(laz[k*2+2], laz[k]);
    }
    dat[k]=g(dat[k], p(laz[k], len));
    laz[k]=d0;
  }
  T update(int a, int b, E x, int k, int l, int r){
    eval(r-l, k);
    if(r<=a||b<=l) return dat[k];
    if(a<=l&&r<=b){
      laz[k] = h(laz[k], x);
      return g(dat[k], p(laz[k], r-l));
    }
    return dat[k] = f(update(a, b, x, k*2+1, l, (l+r)/2),
                      update(a, b, x, k*2+2, (l+r)/2, r));
  }
  T query(int a, int b, int k, int l, int r){
    eval(r-l, k);
    if(r<=a||b<=l) return d1;
    if(a<=l&&r<=b) return dat[k];
    T vl = query(a, b, k*2+1, l, (l+r)/2);
    T vr = query(a, b, k*2+2, (l+r)/2, r);
    return f(vl, vr);
  }
  T update(int a,int b,E x){return update(a,b,x,0,0,n);}
  T query(int a,int b){return query(a,b,0,0,n);}
};

int main(){
  ll n, q;scanf("%lld %lld", &n, &q);
  vector<ar> A(n);
  for(int i=0;i<n;i++){
    ll a;scanf("%lld", &a);
    if(a==1) A[i] = ar{1, 0, 0};
    else A[i] = ar{0, 1, 0};
  }

  SegmentTree<ar, bool> seg(n,
    [&](ar l, ar r){return ar{l[0]+r[0], l[1]+r[1], l[2]+r[2]+l[0]*r[1]};},
    [&](ar l, bool flag){return ar{l[1], l[0], l[0]*l[1]-l[2]};},
    [&](bool l, bool r){return l^r;},
    ar{0, 0, 0}, false, A);

  for(int i=0;i<q;i++){
    ll t, a, b;scanf("%lld %lld %lld", &t, &a, &b);
    if(t==1) seg.update(a-1, b, true);
    else printf("%lld\n", seg.query(a-1, b)[2]);
    /*
    else{
      ar ans = seg.query(a-1, b);
      std::cout << ans[0] << " " << ans[1] << " " << ans[2] << '\n';
    }
    */
  }
}