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 <vector>
using namespace std;

template<class M, class L> struct LazyPropagationSegmentTree
{
	int n;
	int size;
	int log_n;
	vector<M> data;
	vector<L> lazy;
	const function<M(M, M)> f_m;
	const M e_m;
	const function<L(L, L)> f_l;
	const L e_l;
	const function<M(M, L)> f;
	const function<L(L, int)> p;

	LazyPropagationSegmentTree(int n, function<M(M, M)> f_m, M e_m, function<L(L, L)> f_l, L e_l, function<M(M, L)> f, function<L(L, int)> p) : n(n), f_m(f_m), e_m(e_m), f_l(f_l), e_l(e_l), f(f), p(p) {
		size = 1;
		log_n = 0;
		while (size < n) size <<= 1, log_n++;
		data.assign(size * 2, e_m);
		lazy.assign(size * 2, e_l);
	}

	void init(const vector<M> &init_vals) {
		data.assign(size * 2, e_m);
		for (int i = 0; i < init_vals.size(); i++) data[size+i] = init_vals[i];
		for (int i = size-1; i > 0; i--) data[i] = f_m(data[2*i], data[2*i+1]);
	}

	void eval(int k, int len) {
		if (lazy[k] == e_l) return;
		if (k < size) {
			lazy[2*k] = f_l(lazy[2*k], lazy[k]);
			lazy[2*k + 1] = f_l(lazy[2*k + 1], lazy[k]);
		}
		data[k] = f(data[k], p(lazy[k], len));
		lazy[k] = e_l;
	}

	void update(int l, int r, L l_prop) {
		update_aux(l, r, l_prop, 1, 0, size);
	}

	void update_aux(int l, int r, L l_prop, int k, int k_l, int k_r) {
		eval(k, k_r - k_l);
		if (r <= k_l || k_r <= l) return;
		else if (l <= k_l && k_r <= r) {
			lazy[k] = f_l(lazy[k], l_prop);
			eval(k, k_r - k_l);
		} else {
			update_aux(l, r, l_prop, 2*k, k_l, (k_l + k_r) / 2);
			update_aux(l, r, l_prop, 2*k + 1, (k_l + k_r) / 2, k_r);
			data[k] = f_m(data[2*k], data[2*k + 1]);
		}
	}

	M query_all() {
		eval(1, size);
		return data[1];
	}

	M query(int l, int r) {
		return query_aux(l, r, 1, 0, size);
	}

	M query_aux(int l, int r, int k, int k_l, int k_r) {
		eval(k, k_r - k_l);
		if (r <= k_l || k_r <= l) return e_m;
		else if (l <= k_l && k_r <= r) return data[k];
		else {
			M vl = query_aux(l, r, k*2, k_l, (k_l + k_r) / 2);
			M vr = query_aux(l, r, k*2 + 1, (k_l + k_r) / 2, k_r);
			return f_m(vl, vr);
		}
	}

	int find_max_right(int l, const function<bool(M)> &g) {
		if (l == n) return n;
		l += size;
		M s = e_m;
		for (int i = log_n, len = size; i >= 0; i--, len >>= 1) eval(l>>i, len);
		int len = 1;
		while (true) {
			while (l % 2 == 0) l >>= 1, len <<= 1;
			eval(l, len);
			if (!g(f_m(s, data[l]))) break;
			s = f_m(s, data[l]);
			l++;
			if ((l & -l) == l) return n;
		}
		while (l < size) {
			l = 2 * l, len >>= 1;
			eval(l, len);
			if (g(f_m(s, data[l]))) {
				s = f_m(s, data[l]);
				l++;
			}
		}
		return l - size;
	}

	int find_min_left(int r, const function<bool(M)> &g) {
		if (r == 0) return 0;
		r += size;
		M s = e_m;
		for (int i = log_n, len = size; i >= 0; i--, len >>= 1) eval((r-1)>>i, len);
		int len = 1;
		while (true) {
			r--;
			while (r > 1 && (r % 2)) r >>= 1, len <<= 1;
			eval(r, len);
			if (!g(f_m(data[r], s))) break;
			s = f_m(data[r], s);
			if ((r & -r) == r) return 0;
		}
		while (r < size) {
			r = 2 * r + 1, len >>= 1;
			eval(r, len);
			if (g(f_m(data[r], s))) {
				s = f_m(data[r], s);
				r--;
			}
		}
		return r + 1 - size;
	}

	void eval_all() {
		int len = size, j = 2;
		for (int i = 1; i < 2*size; i++) {
			if (i == j) j *= 2, len /= 2;
			eval(i, len);
		}
	}

	M val(int idx) {
		return data[size + idx];
	}

	vector<M> val_vec() {
		vector<M> res(n);
		for (int i = 0; i < n; i++) res[i] = data[size+i];
		return res;
	}
};

int main() {
	int n, Q;
	cin >> n >> Q;
	struct M
	{
		long long t, tr;
		int one, zero;
	};
	using L = int;
	M e_m = {0, 0, 0, 0};
	L e_l = 0;
	auto f_m = [&](M m1, M m2) -> M {
		return {m1.t + m2.t + (long long)m1.one * m2.zero, m1.tr + m2.tr + (long long)m1.zero * m2.one, m1.one + m2.one, m1.zero + m2.zero};
	};
	auto f_l = [&](L l1, L l2) -> L {
		return (l1 + l2) % 2;
	};
	auto f = [&](M m, L l) -> M {
		if (l == e_l) return m;
		return {m.tr, m.t, m.zero, m.one};
	};
	auto p = [&](L l, int len) -> L {
		return l;
	};
	LazyPropagationSegmentTree<M, L> st(n, f_m, e_m, f_l, e_l, f, p);
	vector<M> v(n, e_m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &v[i].one);
		v[i].zero = 1 - v[i].one;
	}
	st.init(v);
	for (int q = 0; q < Q; q++) {
		int t, l, r;
		scanf("%d%d%d", &t, &l, &r);
		l--;
		if (t == 1) {
			st.update(l, r, 1);
		} else {
			long long ans = st.query(l, r).t;
			printf("%lld\n", ans);
		}
	}
	return 0;
}