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:
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

template <class S, class F>
struct SegTreeL {
  using FX = function<S(S, S)>;
  using FA = function<S(S, F)>;
  using FF = function<F(F, F)>;
  int n, _n, log;
  FX fx;
  FA fa;
  FF ff;
  const S es;
  const F ef;
  vector<S> dat;
  vector<F> laz;
  SegTreeL(int n_, FX fx_, FA fa_, FF ff_, S es_, F ef_)
    : fx(fx_), fa(fa_), ff(ff_), es(es_), ef(ef_), n(1), _n(n_), log(__builtin_ctz(n_)) {
      while(n_ > n) n <<= 1;
      dat.assign(n*2-1, es);
      laz.assign(n*2-1, ef);
  }
  SegTreeL(vector<S> &v, FX fx_, FA fa_, FF ff_, S es_, F ef_)
    : fx(fx_), fa(fa_), ff(ff_), es(es_), ef(ef_), n(1), _n(int(v.size())), log(__builtin_ctz(_n)) {
      while(_n > n) n <<= 1;
      dat.assign(n*2-1, es);
      laz.assign(n*2-1, ef);
      copy(v.begin(), v.end(), dat.begin()+n-1);
      build();
  }
  inline int chld(int k) {return k*2+1;}
  inline int chrd(int k) {return k*2+2;}
  void set(int i, S s) {dat[i+n-1] = s;}
  void build() {
    for(int k = n-2; k >= 0; k--) dat[k] = fx(dat[chld(k)], dat[chrd(k)]);
  }
  void eval(int k) {
    if(laz[k] == ef) return;
    if(k < n-1) {
      laz[chld(k)] = ff(laz[chld(k)], laz[k]);
      laz[chrd(k)] = ff(laz[chrd(k)], laz[k]);
    }
    dat[k] = fa(dat[k], laz[k]);
    laz[k] = ef;
  }
  void update(int a, int b, F x, int k, int l, int r) {
    eval(k);
    if(a <= l and r <= b) {
      laz[k] = ff(laz[k], x);
      eval(k);
    }
    else if(a < r and l < b) {
      update(a, b, x, chld(k), l, (l+r)>>1);
      update(a, b, x, chrd(k), (l+r)>>1, r);
      dat[k] = fx(dat[chld(k)], dat[chrd(k)]);
    }
  }
  void update(int a, int b, F x) {update(a, b, x, 0, 0, n);}
  S query(int a, int b, int k, int l, int r) {
    eval(k);
    if(r <= a or b <= l) return es;
    else if(a <= l and r <= b) return dat[k];
    else {
      S vl = query(a, b, chld(k), l, (l+r)>>1);
      S vr = query(a, b, chrd(k), (l+r)>>1, r);
      return fx(vl, vr);
    }
  }
  S query(int a, int b) {return query(a, b, 0, 0, n);}
  template<class G>
  int max_right(int l, G g) {
    assert(g(es));
    if(l == _n) return _n;
    l += n;
    for(int i = log; i >= 0; i--) eval((l>>i)-1);
    S now = es;
    do{
      while(~l&1) l >>= 1;
      if(!g(fx(now, dat[l-1]))) {
        while(l < n) {
          eval(l-1);
          l <<= 1;
          if(g(fx(now, dat[l-1]))) {
            now = fx(now, dat[l++ - 1]);
          }
        }
        return l-n;
      }
      now = fx(now, dat[l++ - 1]);
    } while((l & -l) != l);
    return _n;
  }
  template<class G>
  int min_left(int r, G g) {
    assert(g(es));
    if(r == 0) return 0;
    r += n;
    for(int i = log; i >= 0; i--) eval(((r-1)>>i)-1);
    S now = es;
    do{
      r--;
      while(r > 1 and (r&1)) r >>= 1;
      if(!g(fx(dat[r-1], now))) {
        while(r < n) {
          eval(r-1);
          r = chld(r);
          if(g(fx(dat[r-1], now))) {
            now = fx(dat[--r], now);
          }
        }
        return r+1-n;
      }
      now = fx(dat[r-1], now);
    } while((r & -r) != r);
    return 0;
  }
  //debug
  inline const S operator[](const int i) {return query(i, i+1);}
  void print() {for(int i = 0; i < n; i++) cout << (*this)[i] << (i == n-1?'\n':' ');}
};


//head

struct S {
  int zero, one;
  ll sum;
};
ostream &operator<<(ostream &os, const S &S) {return os << S.zero << ' ' << S.one << ' ' << S.sum << '\n';}
using F = short;
auto fx = [](S a, S b)->S {
  return S{a.zero+b.zero, a.one+b.one, ll(a.one)*b.zero+a.sum+b.sum};
};
auto fa = [](S a, F b)->S {
  return S{a.one, a.zero, ll(a.one)*a.zero - a.sum};
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  SegTreeL<S, F> seg(n, fx, fa, [](F a, F b)->F {return a^b;}, (S){0, 0, 0}, 0);
  rep(i, n) {
    int a;
    cin >> a;
    if(!a) seg.set(i, {1, 0, 0});
    else seg.set(i, {0, 1, 0});
  }
  seg.build();
  while(q--) {
    int type, l, r;
    cin >> type >> l >> r;
    if(type == 1) {
      seg.update(l-1, r, __SHRT_MAX__);
      //seg.print();
    }
    else {
      cout << seg.query(l-1, r).sum << '\n';
    }
  }
}