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:
//#line 1 "test/lazy_segment_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"

//#line 2 "other/bit_width.cpp"

//#line 2 "other/countl_zero.cpp"

//#line 2 "other/countr_zero.cpp"

//#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
//#line 4 "other/countr_zero.cpp"

#include <array>

usize countr_zero(u64 x) {
  if (x == 0)
    return 64;
#ifdef __GNUC__
  return __builtin_ctzll(x);
#else
  constexpr std::array<usize, 64> table = {
      0,  1,  2,  7,  3,  13, 8,  27, 4,  33, 14, 36, 9,  49, 28, 19,
      5,  25, 34, 17, 15, 53, 37, 55, 10, 46, 50, 39, 29, 42, 20, 57,
      63, 6,  12, 26, 32, 35, 48, 18, 24, 16, 52, 54, 45, 38, 41, 56,
      62, 11, 31, 47, 23, 51, 44, 40, 61, 30, 22, 43, 60, 21, 59, 58 };
  return table[(x & ~x + 1) * 0x218A7A392DD9ABF >> 58 & 0x3F];
#endif
}
//#line 5 "other/countl_zero.cpp"

usize countl_zero(u64 x) {
#ifdef __GNUC__
  return x == 0 ? 64 : __builtin_clzll(x);
#else
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x |= x >> 32;
  return 64 - countr_zero(~x);
#endif
}
//#line 5 "other/bit_width.cpp"

usize bit_width(const u64 x) { return 64 - countl_zero(x); }
//#line 4 "data_structure/lazy_segment_tree.cpp"

#include <cassert>
//#line 7 "data_structure/lazy_segment_tree.cpp"
#include <vector>

template <class A> class lazy_segment_tree {
  using V = typename A::value_structure;
  using T = typename V::value_type;
  using O = typename A::operator_structure;
  using E = typename O::value_type;

  class node_type {
  public:
    T value;
    E lazy;

    node_type(const T value, const E lazy) : value(value), lazy(lazy) {}
  };

  static T get(const node_type& x) { return A::operation(x.value, x.lazy); }
  static void add(E& x, const E y) { x = O::operation(x, y); }

  std::vector<node_type> tree;

  void propagate(const usize index) {
    add(tree[index * 2].lazy, tree[index].lazy);
    add(tree[index * 2 + 1].lazy, tree[index].lazy);
    tree[index].lazy = O::identity;
  }

  void propagate_bound(const usize index) {
    if (index == 0)
      return;
    const usize crz = countr_zero(index);
    for (usize h = bit_width(index) - 1; h != crz; h -= 1)
      propagate(index >> h);
  }

  void recalc(const usize index) {
    tree[index].value =
      V::operation(get(tree[index * 2]), get(tree[index * 2 + 1]));
  }

  void recalc_bound(usize index) {
    if (index == 0)
      return;
    index >>= countr_zero(index);
    while (index != 1) {
      index /= 2;
      recalc(index);
    }
  }

public:
  lazy_segment_tree() = default;

  explicit lazy_segment_tree(const usize n)
    : tree(n * 2, node_type(V::identity, O::identity)) {}

  usize size() const { return tree.size() / 2; }

  T fold(usize first, usize last) {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last += size();
    propagate_bound(first);
    recalc_bound(first);
    propagate_bound(last);
    recalc_bound(last);
    T fold_l = V::identity;
    T fold_r = V::identity;
    while (first != last) {
      if (first % 2 != 0) {
        fold_l = V::operation(fold_l, get(tree[first]));
        first += 1;
      }
      first /= 2;
      if (last % 2 != 0) {
        last -= 1;
        fold_r = V::operation(get(tree[last]), fold_r);
      }
      last /= 2;
    }
    return V::operation(fold_l, fold_r);
  }

  void update_range(usize first, usize last, const E x) {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last += size();
    propagate_bound(first);
    propagate_bound(last);
    const usize first_c = first;
    const usize last_c = last;
    while (first != last) {
      if (first % 2 != 0) {
        add(tree[first].lazy, x);
        first += 1;
      }
      first /= 2;
      if (last % 2 != 0) {
        last -= 1;
        add(tree[last].lazy, x);
      }
      last /= 2;
    }
    recalc_bound(first_c);
    recalc_bound(last_c);
  }

  void update_point(usize index, const T x) {
    assert(index < size());
    index += size();
    for (usize h = bit_width(index) - 1; h != 0; h -= 1)
      propagate(index >> h);
    tree[index] = node_type(x, O::identity);
    while (index != 1) {
      index /= 2;
      recalc(index);
    }
  }
};

/**
 * @brief Lazy Segment Tree
 * @see https://scrapbox.io/data-structures/Lazy_Segment_Tree
 */

struct atc {
  usize zero;
  usize one;
  u64 inv;
};

struct atc_op {
  using value_type = atc;
  static atc operation(const atc& l, const atc& r) {
    return atc(
      { l.zero + r.zero, l.one + r.one, l.inv + r.inv + u64(l.one) * r.zero });
  }
  static constexpr atc identity = atc({ 0, 0, 0 });
};

struct atc_act {
  using value_type = bool;
  static bool operation(const bool l, const bool r) { return l != r; }
  static constexpr bool identity = false;
};

struct atc_lst {
  using value_structure = atc_op;
  using operator_structure = atc_act;
  static atc operation(const atc& l, const bool r) {
    if (r) {
      const u64 s = l.zero + l.one;
      const u64 z = l.zero;
      const u64 o = l.one;
      return atc({ l.one, l.zero, s * (s - 1) / 2 - l.inv - z * (z - 1) / 2 - o * (o - 1) / 2});
    }
    else {
      return l;
    }
  }
};

#include <iostream>

int main() {
  //#line 1 "other/fast_ios.cpp"
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //#line 11 "test/lazy_segment_tree.test.cpp"

  int n, q;
  std::cin >> n >> q;
  lazy_segment_tree<atc_lst> lst(n);
  for (int i = 0; i != n; i += 1) {
    usize a;
    std::cin >> a;
    lst.update_point(i, atc({ 1 - a, a, 0 }));
  }
  for (int i = 0; i != q; i += 1) {
    int t;
    std::cin >> t;
    --t;
    switch (t) {
    case 0: {
      usize l, r;
      std::cin >> l >> r;
      --l;
      lst.update_range(l, r, true);
    } break;
    case 1: {
      usize l, r;
      std::cin >> l >> r;
      --l;
      std::cout << lst.fold(l, r).inv << "\n";
    } break;
    }
  }
  return 0;
}