AtCoder Library Practice Contest - Lazy Segment Tree

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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
input = lambda : sys.stdin.readline().rstrip()

class LazySegmentTree:

	def __init__(self, init, unitX, unitA, f, g, h):
		self.f = f
		self.g = g
		self.h = h
		self.unitX = unitX
		self.unitA = unitA
		self.f = f
		if type(init) == int:
			self.n = init
			self.X = [unitX] * (self.n * 2)
			self.size = [1] * (self.n * 2)
		else:
			self.n = len(init)
			self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
			self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
			for i in range(self.n - 1, 0, -1):
				self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
		for i in range(self.n - 1, 0, -1):
			self.size[i] = self.size[i * 2] + self.size[i * 2 | 1]
		self.A = [unitA] * (self.n * 2)

	def update(self, i, x):
		i += self.n
		self.X[i] = x
		i >>= 1
		while i:
			self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
			i >>= 1

	def calc(self, i):
		return self.g(self.X[i], self.A[i], self.size[i])

	def calc_above(self, i):
		i >>= 1
		while i:
			self.X[i] = self.f(self.calc(i * 2), self.calc(i * 2 | 1))
			i >>= 1

	def propagate(self, i):
		self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
		self.A[i * 2] = self.h(self.A[i * 2], self.A[i])
		self.A[i * 2 | 1] = self.h(self.A[i * 2 | 1], self.A[i])
		self.A[i] = self.unitA

	def propagate_above(self, i):
		H = i.bit_length()
		for h in range(H, 0, -1):
			self.propagate(i >> h)

	def propagate_all(self):
		for i in range(1, self.n):
			self.propagate(i)

	def getrange(self, l, r):
		l += self.n
		r += self.n
		(l0, r0) = (l // (l & -l), r // (r & -r) - 1)
		self.propagate_above(l0)
		self.propagate_above(r0)
		al = self.unitX
		ar = self.unitX
		while l < r:
			if l & 1:
				al = self.f(al, self.calc(l))
				l += 1
			if r & 1:
				r -= 1
				ar = self.f(self.calc(r), ar)
			l >>= 1
			r >>= 1
		return self.f(al, ar)

	def getvalue(self, i):
		i += self.n
		self.propagate_above(i)
		return self.calc(i)

	def operate_range(self, l, r, a):
		l += self.n
		r += self.n
		(l0, r0) = (l // (l & -l), r // (r & -r) - 1)
		self.propagate_above(l0)
		self.propagate_above(r0)
		while l < r:
			if l & 1:
				self.A[l] = self.h(self.A[l], a)
				l += 1
			if r & 1:
				r -= 1
				self.A[r] = self.h(self.A[r], a)
			l >>= 1
			r >>= 1
		self.calc_above(l0)
		self.calc_above(r0)

	def max_right(self, l, z):
		if l >= self.n:
			return self.n
		l += self.n
		s = self.unitX
		while 1:
			while l % 2 == 0:
				l >>= 1
			if not z(self.f(s, self.calc(l))):
				while l < self.n:
					l *= 2
					if z(self.f(s, self.calc(l))):
						s = self.f(s, self.calc(l))
						l += 1
				return l - self.n
			s = self.f(s, self.calc(l))
			l += 1
			if l & -l == l:
				break
		return self.n

	def min_left(self, r, z):
		if r <= 0:
			return 0
		r += self.n
		s = self.unitX
		while 1:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not z(self.f(self.calc(r), s)):
				while r < self.n:
					r = r * 2 + 1
					if z(self.f(self.calc(r), s)):
						s = self.f(self.calc(r), s)
						r -= 1
				return r + 1 - self.n
			s = self.f(self.calc(r), s)
			if r & -r == r:
				break
		return 0

	def debug(self):
		X = self.X
		print('X =', [self.calc(i) for i in range(self.n, self.n * 2)])
if False:
	f = lambda x, y: (x[0] + y[0] + x[2] * y[1], x[1] + y[1], x[2] + y[2])
	g = lambda x, a, s: (x[1] * x[2] - x[0], x[2], x[1]) if a else x
	h = lambda a, b: a ^ b
	unitX = (0, 0, 0)
	unitA = 0
mm = (1 << 18) - 1
mmm = (1 << 18) - 1 << 18

def f(x, y):
	return x + y + ((x & mm) * (y & mmm) << 18)

def g(x, a, s):
	(x0, x1, x2) = (x >> 36, x >> 18 & mm, x & mm)
	return (x1 * x2 - x0 << 36) + (x2 << 18) + x1 if a else x

def h(a, b):
	return a ^ b
unitX = 0
unitA = 0
(N, Q) = map(int, input().split())
A = [1 << 18 if int(a) == 0 else 1 for a in input().split()]
st = LazySegmentTree(A, unitX, unitA, f, g, h)
for _ in range(Q):
	(t, l, r) = map(int, input().split())
	if t == 1:
		st.operate_range(l - 1, r, 1)
	else:
		print(st.getrange(l - 1, r) >> 36)


class lazy_segtree:

	def __init__(s, op, e, mapping, composition, id, v):
		if type(v) is int:
			v = [e()] * v
		s._n = len(v)
		s.log = s.ceil_pow2(s._n)
		s.size = 1 << s.log
		s.d = [e()] * (2 * s.size)
		s.lz = [id()] * s.size
		s.e = e
		s.op = op
		s.mapping = mapping
		s.composition = composition
		s.id = id
		for i in range(s._n):
			s.d[s.size + i] = v[i]
		for i in range(s.size - 1, 0, -1):
			s.update(i)

	def set(s, p, x):
		p += s.size
		for i in range(s.log, 0, -1):
			s.push(p >> i)
		s.d[p] = x
		for i in range(1, s.log + 1):
			s.update(p >> i)

	def get(s, p):
		p += s.size
		for i in range(s.log, 0, -1):
			s.push(p >> i)
		return s.d[p]

	def prod(s, l, r):
		if l == r:
			return s.e()
		l += s.size
		r += s.size
		for i in range(s.log, 0, -1):
			if l >> i << i != l:
				s.push(l >> i)
			if r >> i << i != r:
				s.push(r >> i)
		(sml, smr) = (s.e(), s.e())
		while l < r:
			if l & 1:
				sml = s.op(sml, s.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = s.op(s.d[r], smr)
			l >>= 1
			r >>= 1
		return s.op(sml, smr)

	def all_prod(s):
		return s.d[1]

	def apply(s, p, f):
		p += s.size
		for i in range(s.log, 0, -1):
			s.push(p >> i)
		s.d[p] = s.mapping(f, s.d[p])
		for i in range(1, s.log + 1):
			s.update(p >> i)

	def apply(s, l, r, f):
		if l == r:
			return
		l += s.size
		r += s.size
		for i in range(s.log, 0, -1):
			if l >> i << i != l:
				s.push(l >> i)
			if r >> i << i != r:
				s.push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				sml = s.all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				smr = s.all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, s.log + 1):
			if l >> i << i != l:
				s.update(l >> i)
			if r >> i << i != r:
				s.update(r - 1 >> i)

	def max_right(s, l, g):
		if l == s._n:
			return s._n
		l += s.size
		for i in range(s.log, 0, -1):
			s.push(l >> i)
		sm = s.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(s.op(sm, s.d[l])):
				while l < s.size:
					s.push(l)
					l = 2 * l
					if g(s.op(sm, s.d[l])):
						sm = s.op(sm, s.d[l])
						l += 1
				return l - s.size
			sm = s.op(sm, s.d[l])
			l += 1
			if l & -l == l:
				break
		return s._n

	def min_left(s, r, g):
		if r == 0:
			return 0
		r += s.size
		for i in range(s.log, 0, -1):
			s.push(r - 1 >> i)
		sm = s.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(s.op(s.d[r], sm)):
				while r < s.size:
					s.push(r)
					r = 2 * r + 1
					if g(s.op(s.d[r], sm)):
						sm = s.op(s.d[r], sm)
						r -= 1
				return r + 1 - s.size
			sm = s.op(s.d[r], sm)
			if r & -r == r:
				break
		return 0

	def update(s, k):
		s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])

	def all_apply(s, k, f):
		s.d[k] = s.mapping(f, s.d[k])
		if k < s.size:
			s.lz[k] = s.composition(f, s.lz[k])

	def push(s, k):
		s.all_apply(2 * k, s.lz[k])
		s.all_apply(2 * k + 1, s.lz[k])
		s.lz[k] = s.id()

	def ceil_pow2(s, n):
		x = 0
		while 1 << x < n:
			x += 1
		return x

def op(l, r):
	return [l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0]]

def e():
	return [0, 0, 0]

def mapping(l, r):
	if not l:
		return r
	return [r[1], r[0], r[1] * r[0] - r[2]]

def composition(l, r):
	return l and (not r) or (not l and r)

def id():
	return False

def g(x):
	return x[2] <= 1
import sys
input = sys.stdin.readline
(N, Q) = list(map(int, input().split()))
a = [(0, 1, 0) if A == '1' else (1, 0, 0) for A in input().split()]
seg = lazy_segtree(op, e, mapping, composition, id, a)
ans = []
for i in range(Q):
	(t, l, r) = list(map(int, input().split()))
	l -= 1
	if t == 1:
		seg.apply(l, r, True)
	else:
		ans.append(seg.prod(l, r)[2])
for i in ans:
	print(i)


class lazy_segtree:

	def __init__(s, op, e, mapping, composition, id, v):
		if type(v) is int:
			v = [e()] * v
		s._n = len(v)
		s.log = s.ceil_pow2(s._n)
		s.size = 1 << s.log
		s.d = [e()] * (2 * s.size)
		s.lz = [id()] * s.size
		s.e = e
		s.op = op
		s.mapping = mapping
		s.composition = composition
		s.id = id
		for i in range(s._n):
			s.d[s.size + i] = v[i]
		for i in range(s.size - 1, 0, -1):
			s.update(i)

	def set(s, p, x):
		p += s.size
		for i in range(s.log, 0, -1):
			s.push(p >> i)
		s.d[p] = x
		for i in range(1, s.log + 1):
			s.update(p >> i)

	def get(s, p):
		p += s.size
		for i in range(s.log, 0, -1):
			s.push(p >> i)
		return s.d[p]

	def prod(s, l, r):
		if l == r:
			return s.e()
		l += s.size
		r += s.size
		for i in range(s.log, 0, -1):
			if l >> i << i != l:
				s.push(l >> i)
			if r >> i << i != r:
				s.push(r >> i)
		(sml, smr) = (s.e(), s.e())
		while l < r:
			if l & 1:
				sml = s.op(sml, s.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = s.op(s.d[r], smr)
			l >>= 1
			r >>= 1
		return s.op(sml, smr)

	def all_prod(s):
		return s.d[1]

	def apply(s, p, f):
		p += s.size
		for i in range(s.log, 0, -1):
			s.push(p >> i)
		s.d[p] = s.mapping(f, s.d[p])
		for i in range(1, s.log + 1):
			s.update(p >> i)

	def apply(s, l, r, f):
		if l == r:
			return
		l += s.size
		r += s.size
		for i in range(s.log, 0, -1):
			if l >> i << i != l:
				s.push(l >> i)
			if r >> i << i != r:
				s.push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				sml = s.all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				smr = s.all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, s.log + 1):
			if l >> i << i != l:
				s.update(l >> i)
			if r >> i << i != r:
				s.update(r - 1 >> i)

	def max_right(s, l, g):
		if l == s._n:
			return s._n
		l += s.size
		for i in range(s.log, 0, -1):
			s.push(l >> i)
		sm = s.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(s.op(sm, s.d[l])):
				while l < s.size:
					s.push(l)
					l = 2 * l
					if g(s.op(sm, s.d[l])):
						sm = s.op(sm, s.d[l])
						l += 1
				return l - s.size
			sm = s.op(sm, s.d[l])
			l += 1
			if l & -l == l:
				break
		return s._n

	def min_left(s, r, g):
		if r == 0:
			return 0
		r += s.size
		for i in range(s.log, 0, -1):
			s.push(r - 1 >> i)
		sm = s.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(s.op(s.d[r], sm)):
				while r < s.size:
					s.push(r)
					r = 2 * r + 1
					if g(s.op(s.d[r], sm)):
						sm = s.op(s.d[r], sm)
						r -= 1
				return r + 1 - s.size
			sm = s.op(s.d[r], sm)
			if r & -r == r:
				break
		return 0

	def update(s, k):
		s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])

	def all_apply(s, k, f):
		s.d[k] = s.mapping(f, s.d[k])
		if k < s.size:
			s.lz[k] = s.composition(f, s.lz[k])

	def push(s, k):
		s.all_apply(2 * k, s.lz[k])
		s.all_apply(2 * k + 1, s.lz[k])
		s.lz[k] = s.id()

	def ceil_pow2(s, n):
		x = 0
		while 1 << x < n:
			x += 1
		return x

def op(l, r):
	(l0, l1) = (l[0] >> 18, l[0] & 262143)
	(r0, r1) = (r[0] >> 18, r[0] & 262143)
	return [(l0 + r0 << 18) + l1 + r1, l[1] + r[1] + l1 * r0]

def e():
	return [0, 0]

def mapping(l, r):
	if not l:
		return r
	(r0, r1) = (r[0] >> 18, r[0] & 262143)
	return [(r1 << 18) + r0, r1 * r0 - r[1]]

def composition(l, r):
	return l and (not r) or (not l and r)

def id():
	return False

def g(x):
	return x[2] <= 1
(N, Q) = list(map(int, input().split()))
A = list(map(int, input().split()))
TLR = [list(map(int, input().split())) for _ in range(Q)]
a = []
for i in A:
	if i == 0:
		a.append([1 << 18, 0])
	else:
		a.append([1, 0])
_ = 0
seg = lazy_segtree(op, e, mapping, composition, id, a)
for i in range(Q):
	(t, l, r) = TLR[i]
	l -= 1
	if t == 1:
		seg.apply(l, r, True)
	else:
		print(seg.prod(l, r)[1])


class LazySegmentTree:
	__slots__ = ['n', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

	def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
		self.me = monoid_identity
		self.oe = operator_identity
		self.fmm = func_monoid_monoid
		self.fmo = func_monoid_operator
		self.foo = func_operator_operator
		self.n = len(monoid_data)
		self.data = monoid_data * 2
		for i in range(self.n - 1, 0, -1):
			self.data[i] = self.fmm(self.data[2 * i], self.data[2 * i + 1])
		self.lazy = [self.oe] * (self.n * 2)

	def replace(self, index, value):
		index += self.n
		for shift in range(index.bit_length() - 1, 0, -1):
			i = index >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		self.data[index] = value
		self.lazy[index] = self.oe
		i = index
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def effect(self, l, r, operator):
		l += self.n
		r += self.n
		indices = []
		l0 = l // (l & -l) // 2
		r0 = (r // (r & -r) - 1) // 2
		while r0 > l0:
			indices.append(r0)
			r0 //= 2
		while l0 > r0:
			indices.append(l0)
			l0 //= 2
		while l0 and l0 != r0:
			indices.append(r0)
			r0 //= 2
			if l0 == r0:
				break
			indices.append(l0)
			l0 //= 2
		while r0:
			indices.append(r0)
			r0 //= 2
		for i in reversed(indices):
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		while l < r:
			if l % 2:
				self.lazy[l] = self.foo(self.lazy[l], operator)
				l += 1
			if r % 2:
				r -= 1
				self.lazy[r] = self.foo(self.lazy[r], operator)
			l //= 2
			r //= 2
		for i in indices:
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def folded(self, l, r):
		l += self.n
		r += self.n
		indices = []
		l0 = l // (l & -l) // 2
		r0 = (r // (r & -r) - 1) // 2
		while r0 > l0:
			indices.append(r0)
			r0 //= 2
		while l0 > r0:
			indices.append(l0)
			l0 //= 2
		while l0 and l0 != r0:
			indices.append(r0)
			r0 //= 2
			if l0 == r0:
				break
			indices.append(l0)
			l0 //= 2
		while r0:
			indices.append(r0)
			r0 //= 2
		for i in reversed(indices):
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		left_folded = self.me
		right_folded = self.me
		while l < r:
			if l % 2:
				left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
			l //= 2
			r //= 2
		return self.fmm(left_folded, right_folded)

def atc2():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	monoid_data = [(0, 1, 0) if A == b'1' else (1, 0, 0) for A in input().split()]

	def fmm(m1, m2):
		return (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0])

	def fmo(m1, o1):
		if o1:
			return (m1[1], m1[0], m1[0] * m1[1] - m1[2])
		else:
			return m1

	def foo(o1, o2):
		return o1 ^ o2
	lst = LazySegmentTree(monoid_data, (0, 0, 0), 0, fmm, fmo, foo)
	ans = []
	for _ in range(Q):
		(T, L, R) = map(int, input().split())
		if T == 1:
			lst.effect(L - 1, R, 1)
		else:
			ans.append(lst.folded(L - 1, R)[2])
	print('\n'.join(map(str, ans)))
atc2()


class LazySegmentTree:

	def __init__(self, n, op, e, mapping, composition, id):
		self.n = n
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self.log = (n - 1).bit_length()
		self.size = 1 << self.log
		self.d = [e] * (2 * self.size)
		self.lz = [id] * self.size

	def update(self, k):
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

	def all_apply(self, k, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def push(self, k):
		self.all_apply(2 * k, self.lz[k])
		self.all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id

	def build(self, arr):
		for (i, a) in enumerate(arr):
			self.d[self.size + i] = a
		for i in range(1, self.size)[::-1]:
			self.update(i)

	def set(self, p, x):
		p += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def get(self, p):
		p += self.size
		for i in range(1, self.log + 1):
			self.push(p >> i)
		return self.d[p]

	def prod(self, l, r):
		if l == r:
			return self.e
		l += self.size
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r >> i)
		sml = smr = self.e
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p, f):
		p += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def range_apply(self, l, r, f):
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r - 1 >> i)
		l2 = l
		r2 = r
		while l < r:
			if l & 1:
				self.all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.all_apply(r, f)
			l >>= 1
			r >>= 1
		l = l2
		r = r2
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.update(l >> i)
			if r >> i << i != r:
				self.update(r - 1 >> i)

	def max_right(self, l, g):
		if l == self.n:
			return self.n
		l += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(l >> i)
		sm = self.e
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				return self.n

	def min_left(self, r, g):
		if r == 0:
			return 0
		r += self.size
		for i in range(1, self.log + 1)[::-1]:
			self.push(r - 1 >> i)
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				return 0
import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())

def op(x, y):
	(x0, x1, x2) = x
	(y0, y1, y2) = y
	return (x0 + y0, x1 + y1, x2 + y2 + x1 * y0)

def mapping(p, x):
	(x0, x1, x2) = x
	if p:
		return (x1, x0, x0 * x1 - x2)
	else:
		return (x0, x1, x2)

def composition(p, q):
	return p ^ q
lst = LazySegmentTree(N, op, (0, 0, 0), mapping, composition, 0)
lst.build(((1 - a, a, 0) for a in map(int, input().split())))
res = list()
for _ in range(Q):
	(t, l, r) = map(int, input().split())
	if t == 1:
		lst.range_apply(l - 1, r, 1)
	else:
		res.append(lst.prod(l - 1, r)[2])
print('\n'.join(map(str, res)))


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

class lazy_segtree:

	def __init__(self, op, e, mapping, composition, id, v: list):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self._n = len(v)
		self.log = self.__ceil_pow2(self._n)
		self.size = 1 << self.log
		self.lz = [self.id()] * self.size
		self.d = [self.e()] * (2 * self.size)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return self.e()
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r >> i)
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p: int, f: bool):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def apply(self, l: int, r: int, f: bool):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.__all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.__all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.__update(l >> i)
			if r >> i << i != r:
				self.__update(r >> i)

	def max_right(self, l: int, g):
		assert 0 <= l and l <= self._n
		if l == self._n:
			return self._n
		l += self.size
		for i in range(self.log, 0, -1):
			self.__push(l >> i)
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.__push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l != l:
				break
		return self._n

	def min_left(self, r: int, g):
		assert 0 <= r and r <= self._n
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.__push(r >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.__push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r += 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r != r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

	def __all_apply(self, k: int, f: bool):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k: int):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id()

	def __ceil_pow2(self, n: int) -> int:
		x = 0
		while 1 << x < n:
			x += 1
		return x

def op(l: tuple, r: tuple):
	return (l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0])

def e():
	return (0, 0, 0)

def mapping(l: bool, r: tuple):
	if not l:
		return r
	return (r[1], r[0], r[1] * r[0] - r[2])

def composition(l: bool, r: bool):
	return l ^ r

def id():
	return False

def Main():
	(n, q) = read_ints()
	A = read_int_list()
	query = [read_ints() for _ in range(q)]
	a = [(1, 0, 0) if i == 0 else (0, 1, 0) for i in A]
	seg = lazy_segtree(op, e, mapping, composition, id, a)
	for (t, l, r) in query:
		if t == 1:
			seg.apply(~-l, r, True)
		else:
			print(seg.prod(~-l, r)[2])
Main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')

class LazySegmentTree:

	def __init__(self, n, a=None):
		num = 1
		v = 0
		while num <= n:
			num *= 2
			v += 1
		self.q = [None] * (2 * v + 10)
		self.num = num
		self.seg = [ninf] * (2 * self.num - 1)
		self.lazy = [f0] * (2 * self.num - 1)
		self.ls = [0] * (2 * self.num - 1)
		self.rs = [0] * (2 * self.num - 1)
		self.ls[0] = 0
		self.rs[0] = self.num
		for i in range(self.num - 1):
			self.ls[2 * i + 1] = self.ls[i]
			self.rs[2 * i + 1] = (self.ls[i] + self.rs[i]) // 2
			self.ls[2 * i + 2] = (self.ls[i] + self.rs[i]) // 2
			self.rs[2 * i + 2] = self.rs[i]
		if a is not None:
			assert len(a) == n
			for i in range(n):
				self.seg[num - 1 + i] = a[i]
			for k in range(num - 2, -1, -1):
				self.seg[k] = op(self.seg[2 * k + 1], self.seg[2 * k + 2])

	def eval(self, k):
		if self.lazy[k] == f0:
			return
		if k < self.num - 1:
			self.lazy[k * 2 + 1] = composition(self.lazy[k], self.lazy[k * 2 + 1])
			self.lazy[k * 2 + 2] = composition(self.lazy[k], self.lazy[k * 2 + 2])
		self.seg[k] = mapping(self.lazy[k], self.seg[k])
		self.lazy[k] = f0

	def eval_all(self):
		for i in range(2 * self.num - 1):
			self.eval(i)

	def update(self, a, b, x=None, f=None):
		if f is None:
			f = lambda y: x
		k = 0
		self.q[0] = k
		ind = 1
		while ind:
			ind -= 1
			k = self.q[ind]
			(l, r) = (self.ls[k], self.rs[k])
			if k >= 0:
				self.eval(k)
				if r <= a or b <= l:
					continue
				elif a <= l and r <= b:
					self.lazy[k] = composition(f, self.lazy[k])
					self.eval(k)
				else:
					self.q[ind] = ~k
					self.q[ind + 1] = 2 * k + 1
					self.q[ind + 2] = 2 * k + 2
					ind += 3
			else:
				k = ~k
				self.seg[k] = op(self.seg[2 * k + 1], self.seg[2 * k + 2])

	def query(self, a, b):
		k = 0
		l = 0
		r = self.num
		self.q[0] = k
		ind = 1
		ans = ninf
		while ind:
			ind -= 1
			k = self.q[ind]
			(l, r) = (self.ls[k], self.rs[k])
			self.eval(k)
			if r <= a or b <= l:
				continue
			elif a <= l and r <= b:
				ans = op(ans, self.seg[k])
			else:
				self.q[ind] = 2 * k + 2
				self.q[ind + 1] = 2 * k + 1
				ind += 2
		return ans
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
ninf = (0, 0, 0)
op = lambda x, y: (x[0] + y[0] + x[2] * y[1], x[1] + y[1], x[2] + y[2])
mapping = lambda f, x: ((x[1] + x[2]) * (x[1] + x[2] - 1) // 2 - x[1] * (x[1] - 1) // 2 - x[2] * (x[2] - 1) // 2 - x[0], x[2], x[1]) if f else x
composition = lambda f1, f2: f1 ^ f2
f0 = False
sg = LazySegmentTree(n, [(0, 1, 0) if item == 0 else (0, 0, 1) for item in a])
ans = []
for _ in range(q):
	t = tuple(map(int, input().split()))
	if t[0] == 1:
		(_, l, r) = t
		sg.update(l - 1, r, f=True)
	else:
		(_, l, r) = t
		ans.append(sg.query(l - 1, r)[0])
write('\n'.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 9 + 1
MOD = 998244353

def set_depth(depth):
	global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
	DEPTH = depth
	SEGTREE_SIZE = 1 << DEPTH
	NONLEAF_SIZE = 1 << DEPTH - 1

def set_width(width):
	set_depth((width - 1).bit_length() + 1)

def get_size(pos):
	ret = pos.bit_length()
	return 1 << DEPTH - ret

def up(pos):
	pos += SEGTREE_SIZE // 2
	return pos // (pos & -pos)

def up_propagate(table, pos, binop):
	while pos > 1:
		pos >>= 1
		table[pos] = binop(table[pos * 2], table[pos * 2 + 1])

def full_up(table, binop):
	for i in range(NONLEAF_SIZE - 1, 0, -1):
		table[i] = binop(table[2 * i], table[2 * i + 1])

def force_down_propagate(action_table, value_table, pos, action_composite, action_force, action_unity):
	max_level = pos.bit_length() - 1
	size = NONLEAF_SIZE
	for level in range(max_level):
		size //= 2
		i = pos >> max_level - level
		action = action_table[i]
		if action != action_unity:
			action_table[i * 2] = action_composite(action, action_table[i * 2])
			action_table[i * 2 + 1] = action_composite(action, action_table[i * 2 + 1])
			action_table[i] = action_unity
			value_table[i * 2] = action_force(action, value_table[i * 2], size)
			value_table[i * 2 + 1] = action_force(action, value_table[i * 2 + 1], size)

def force_range_update(value_table, action_table, left, right, action, action_force, action_composite, action_unity):
	left += NONLEAF_SIZE
	right += NONLEAF_SIZE
	while left < right:
		if left & 1:
			value_table[left] = action_force(action, value_table[left], get_size(left))
			action_table[left] = action_composite(action, action_table[left])
			left += 1
		if right & 1:
			right -= 1
			value_table[right] = action_force(action, value_table[right], get_size(right))
			action_table[right] = action_composite(action, action_table[right])
		left //= 2
		right //= 2

def range_reduce(table, left, right, binop, unity):
	ret_left = unity
	ret_right = unity
	left += NONLEAF_SIZE
	right += NONLEAF_SIZE
	while left < right:
		if left & 1:
			ret_left = binop(ret_left, table[left])
			left += 1
		if right & 1:
			right -= 1
			ret_right = binop(table[right], ret_right)
		left //= 2
		right //= 2
	return binop(ret_left, ret_right)

def lazy_range_update(action_table, value_table, start, end, action, action_composite, action_force, action_unity, value_binop):
	L = up(start)
	R = up(end)
	force_down_propagate(action_table, value_table, L, action_composite, action_force, action_unity)
	force_down_propagate(action_table, value_table, R, action_composite, action_force, action_unity)
	force_range_update(value_table, action_table, start, end, action, action_force, action_composite, action_unity)
	up_propagate(value_table, L, value_binop)
	up_propagate(value_table, R, value_binop)

def lazy_range_reduce(action_table, value_table, start, end, action_composite, action_force, action_unity, value_binop, value_unity):
	force_down_propagate(action_table, value_table, up(start), action_composite, action_force, action_unity)
	force_down_propagate(action_table, value_table, up(end), action_composite, action_force, action_unity)
	return range_reduce(value_table, start, end, value_binop, value_unity)

def debugprint(xs, minsize=0, maxsize=None):
	global DEPTH
	strs = [str(x) for x in xs]
	if maxsize != None:
		for i in range(NONLEAF_SIZE, SEGTREE_SIZE):
			strs[i] = strs[i][:maxsize]
	s = max((len(s) for s in strs[NONLEAF_SIZE:]))
	if s > minsize:
		minsize = s
	result = ['|'] * DEPTH
	level = 0
	next_level = 2
	for i in range(1, SEGTREE_SIZE):
		if i == next_level:
			level += 1
			next_level *= 2
		width = (minsize + 1 << DEPTH - 1 - level) - 1
		result[level] += strs[i].center(width) + '|'
	print(*result, sep='\n', file=sys.stderr)

def debug(*x):
	print(*x, file=sys.stderr)

def solve(SOLVE_PARAMS):
	pass

def main():
	(N, Q) = map(int, input().split())
	AS = list(map(int, input().split()))
	set_width(N)
	value_unity = (0, 0, 0)
	value_table = [value_unity] * SEGTREE_SIZE
	value_table[NONLEAF_SIZE:NONLEAF_SIZE + len(AS)] = [(0, 1, 0) if a else (1, 0, 0) for a in AS]

	def value_binop(a, b):
		(x1, y1, z1) = a
		(x2, y2, z2) = b
		return (x1 + x2, y1 + y2, z1 + z2 + y1 * x2)
	full_up(value_table, value_binop)
	action_unity = False
	action_table = [action_unity] * SEGTREE_SIZE

	def action_force(action, value, size):
		if action == action_unity:
			return value
		(x, y, z) = value
		return (y, x, x * y - z)

	def action_composite(new_action, old_action):
		return new_action ^ old_action
	for _q in range(Q):
		(q, *args) = map(int, input().split())
		if q == 1:
			(l, r) = args
			l -= 1
			lazy_range_update(action_table, value_table, l, r, True, action_composite, action_force, action_unity, value_binop)
		else:
			(l, r) = args
			l -= 1
			print(lazy_range_reduce(action_table, value_table, l, r, action_composite, action_force, action_unity, value_binop, value_unity)[2])
T1 = '\n5 5\n0 1 0 0 1\n2 1 5\n1 3 4\n2 2 5\n1 1 3\n2 1 2\n'
TEST_T1 = '\n>>> as_input(T1)\n>>> main()\n2\n0\n1\n'

def _test():
	import doctest
	doctest.testmod()
	g = globals()
	for k in sorted(g):
		if k.startswith('TEST_'):
			doctest.run_docstring_examples(g[k], g, name=k)

def as_input(s):
	import io
	f = io.StringIO(s.strip())
	g = globals()
	g['input'] = lambda : bytes(f.readline(), 'ascii')
	g['read'] = lambda : bytes(f.read(), 'ascii')
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
if sys.argv[-1] == '-t':
	print('testing')
	_test()
	sys.exit()
main()


class LazySegmentTree:

	def __init__(self, op, e, mapping, composition, im, init_array):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.im = im
		l = len(init_array)

		def ceil_pow2(n):
			x = 0
			while 1 << x < n:
				x += 1
			return x
		self.log = ceil_pow2(l)
		self.size = 1 << self.log
		self.d = [e() for _ in range(2 * self.size)]
		self.lz = [im() for _ in range(self.size)]
		for (i, a) in enumerate(init_array):
			self.d[i + self.size] = a
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set(self, p, x):
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> i)

	def __getitem__(self, p):
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l, r):
		if l == r:
			return self.e()
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r >> i)
		sml = self.e()
		smr = self.e()
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def apply(self, l, r, f):
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.__all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.__all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.__update(l >> i)
			if r >> i << i != r:
				self.__update(r - 1 >> i)

	def __update(self, k):
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

	def __all_apply(self, k, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.im()

def atcoder_practice_k():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	A = list(map(lambda x: (int(x) << 32) + 1, input().split()))
	MOD = 998244353

	def e():
		return 0

	def op(s, t):
		(sv, sn) = (s >> 32, s % (1 << 32))
		(tv, tn) = (t >> 32, t % (1 << 32))
		return ((sv + tv) % MOD << 32) + sn + tn

	def mapping(f, a):
		(fb, fc) = (f >> 32, f % (1 << 32))
		(av, an) = (a >> 32, a % (1 << 32))
		return ((fb * av + fc * an) % MOD << 32) + an

	def composition(f, g):
		(fb, fc) = (f >> 32, f % (1 << 32))
		(gb, gc) = (g >> 32, g % (1 << 32))
		return (fb * gb % MOD << 32) + (gc * fb + fc) % MOD

	def im():
		return 1 << 32
	st = LazySegmentTree(op, e, mapping, composition, im, A)
	for _ in range(Q):
		(k, *q) = map(int, input().split())
		if k == 0:
			(l, r, b, c) = q
			st.apply(l, r, (b << 32) + c)
		else:
			(l, r) = q
			a = st.prod(l, r)
			print(a >> 32)

def e():
	return (0, 0, 0)

def op(sl, sr):
	return (sl[0] + sr[0], sl[1] + sr[1], sl[2] + sr[2] + sl[1] * sr[0])

def mapping(fl, sr):
	if fl % 2 == 1:
		return (sr[1], sr[0], sr[1] * sr[0] - sr[2])
	return sr

def composition(fl, fr):
	return (fl + fr) % 2

def im():
	return 0

def atcoder_practice_l():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	A = list(map(lambda x: (0, 1, 0) if int(x) == 1 else (1, 0, 0), input().split()))
	st = LazySegmentTree(op, e, mapping, composition, im, A)
	for _ in range(Q):
		(t, l, r) = map(int, input().split())
		l -= 1
		if t == 1:
			st.apply(l, r, 1)
		else:
			a = st.prod(l, r)
			print(a[2])
atcoder_practice_l()


import sys
sys.setrecursionlimit(10 ** 7)

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

class LazySegTree:

	def __init__(self, N, X_func, A_func, operate, X_unit, A_unit):
		self.N = N
		self.X_func = X_func
		self.A_func = A_func
		self.operate = operate
		self.X_unit = X_unit
		self.A_unit = A_unit
		self.X = [self.X_unit] * (2 * self.N)
		self.A = [self.A_unit] * (2 * self.N)
		self.size = [0] * (2 * self.N)

	def build(self, init_value):
		for i in range(self.N):
			self.X[self.N + i] = init_value[i]
			self.size[self.N + i] = 1
		for i in range(self.N - 1, 0, -1):
			self.X[i] = self.X_func(self.X[i << 1], self.X[i << 1 | 1])
			self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

	def update(self, i, x):
		i += self.N
		self.X[i] = x
		i >>= 1
		while i:
			self.X[i] = self.X_func(self.X[i << 1], self.X[i << 1 | 1])
			i >>= 1

	def eval_at(self, i):
		return self.operate(self.X[i], self.A[i], self.size[i])

	def eval_above(self, i):
		i >>= 1
		while i:
			self.X[i] = self.X_func(self.eval_at(i << 1), self.eval_at(i << 1 | 1))
			i >>= 1

	def propagate_at(self, i):
		self.X[i] = self.eval_at(i)
		self.A[i << 1] = self.A_func(self.A[i << 1], self.A[i])
		self.A[i << 1 | 1] = self.A_func(self.A[i << 1 | 1], self.A[i])
		self.A[i] = self.A_unit

	def propagate_above(self, i):
		H = i.bit_length()
		for h in range(H, 0, -1):
			self.propagate_at(i >> h)

	def fold(self, L, R):
		L += self.N
		R += self.N
		L0 = L // (L & -L)
		R0 = R // (R & -R) - 1
		self.propagate_above(L0)
		self.propagate_above(R0)
		vL = self.X_unit
		vR = self.X_unit
		while L < R:
			if L & 1:
				vL = self.X_func(vL, self.eval_at(L))
				L += 1
			if R & 1:
				R -= 1
				vR = self.X_func(self.eval_at(R), vR)
			L >>= 1
			R >>= 1
		return self.X_func(vL, vR)

	def operate_range(self, L, R, x):
		L += self.N
		R += self.N
		L0 = L // (L & -L)
		R0 = R // (R & -R) - 1
		self.propagate_above(L0)
		self.propagate_above(R0)
		while L < R:
			if L & 1:
				self.A[L] = self.A_func(self.A[L], x)
				L += 1
			if R & 1:
				R -= 1
				self.A[R] = self.A_func(self.A[R], x)
			L >>= 1
			R >>= 1
		self.eval_above(L0)
		self.eval_above(R0)
(N, Q) = MI()
A = LI()
B = []
for i in range(N):
	if A[i] == 0:
		B.append((0, 1, 0))
	else:
		B.append((0, 0, 1))

def X_func(x, y):
	(x0, x1, x2) = x
	(y0, y1, y2) = y
	return (x0 + y0 + x2 * y1, x1 + y1, x2 + y2)

def A_func(a, b):
	return a ^ b

def operate(x, a, r):
	if a == 0:
		return x
	(x0, x1, x2) = x
	return (x1 * x2 - x0, x2, x1)
X_unit = (0, 0, 0)
A_unit = 0
LST = LazySegTree(N, X_func, A_func, operate, X_unit, A_unit)
LST.build(B)
for i in range(Q):
	(T, L, R) = MI()
	if T == 1:
		LST.operate_range(L - 1, R, 1)
	else:
		print(LST.fold(L - 1, R)[0])


I = [int(_) for _ in open(0).read().split()]
(N, Q) = I[:2]
A = I[2:2 + N]
T = I[2 + N::3]
L = I[3 + N::3]
R = I[4 + N::3]

class LazySegmentTree:

	def __init__(self, array, f, g, h, ti, ei):
		self.f = f
		self.g = g
		self.h = h
		self.ti = ti
		self.ei = ei
		self.height = height = len(array).bit_length()
		self.n = n = 2 ** height
		self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
		self.laz = [ei] * (2 * n)
		for i in range(n - 1, 0, -1):
			dat[i] = f(dat[i << 1], dat[i << 1 | 1])

	def reflect(self, k):
		dat = self.dat
		ei = self.ei
		laz = self.laz
		g = self.g
		return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

	def evaluate(self, k):
		laz = self.laz
		ei = self.ei
		reflect = self.reflect
		dat = self.dat
		h = self.h
		if laz[k] is ei:
			return
		laz[k << 1 | 0] = h(laz[k << 1 | 0], laz[k])
		laz[k << 1 | 1] = h(laz[k << 1 | 1], laz[k])
		dat[k] = reflect(k)
		laz[k] = ei

	def thrust(self, k):
		height = self.height
		evaluate = self.evaluate
		for i in range(height, 0, -1):
			evaluate(k >> i)

	def recalc(self, k):
		dat = self.dat
		reflect = self.reflect
		f = self.f
		while k:
			k >>= 1
			dat[k] = f(reflect(k << 1 | 0), reflect(k << 1 | 1))

	def update(self, a, b, x):
		thrust = self.thrust
		n = self.n
		h = self.h
		laz = self.laz
		recalc = self.recalc
		a += n
		b += n - 1
		l = a
		r = b + 1
		thrust(a)
		thrust(b)
		while l < r:
			if l & 1:
				laz[l] = h(laz[l], x)
				l += 1
			if r & 1:
				r -= 1
				laz[r] = h(laz[r], x)
			l >>= 1
			r >>= 1
		recalc(a)
		recalc(b)

	def set_val(self, a, x):
		n = self.n
		thrust = self.thrust
		dat = self.dat
		laz = self.laz
		recalc = self.recalc
		ei = self.ei
		a += n
		thrust(a)
		dat[a] = x
		laz[a] = ei
		recalc(a)

	def query(self, a, b):
		f = self.f
		ti = self.ti
		n = self.n
		thrust = self.thrust
		reflect = self.reflect
		a += n
		b += n - 1
		thrust(a)
		thrust(b)
		l = a
		r = b + 1
		vl = vr = ti
		while l < r:
			if l & 1:
				vl = f(vl, reflect(l))
				l += 1
			if r & 1:
				r -= 1
				vr = f(reflect(r), vr)
			l >>= 1
			r >>= 1
		return f(vl, vr)
array = [(0, 0, 0)] + [(0, 1, 0) if a else (1, 0, 0) for a in A]
f = lambda a, b: (a[0] + b[0], a[1] + b[1], a[2] + b[2] + a[1] * b[0])

def g(a, b):
	if b == -1:
		x = a[1]
		y = a[0]
		z = (x + y) * (x + y - 1) // 2 - x * (x - 1) // 2 - y * (y - 1) // 2 - a[2]
		return (x, y, z)
	else:
		return a
h = lambda a, b: a * b
ti = (0, 0, 0)
ei = 1
LST = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
for (t, l, r) in zip(T, L, R):
	r += 1
	if t == 1:
		LST.update(l, r, -1)
	else:
		print(LST.query(l, r)[2])


import sys
readline = sys.stdin.readline
from operator import xor

class Lazysegtree:

	def __init__(self, A, fx, ex, fm, em, fa, initialize=True):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.fm = fm
		self.ex = ex
		self.em = em
		self.lazy = [em] * (2 * self.N0)
		if initialize:
			self.data = [self.ex] * self.N0 + A + [self.ex] * (self.N0 - self.N)
			for i in range(self.N0 - 1, -1, -1):
				self.data[i] = self.fx(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [self.ex] * (2 * self.N0)

	def fx(self, x, y):
		return (x[0] + y[0], x[1] + y[1], x[2] + y[2] + x[1] * y[0])

	def fa(self, ope, idx):
		if ope == 0:
			return self.data[idx]
		(zero, one, t) = self.data[idx]
		return (one, zero, (one + zero) * (one + zero - 1) // 2 - one * (one - 1) // 2 - zero * (zero - 1) // 2 - t)

	def __repr__(self):
		s = 'data'
		l = 'lazy'
		cnt = 1
		for i in range(self.N0.bit_length()):
			s = '\n'.join((s, ' '.join(map(str, self.data[cnt:cnt + (1 << i)]))))
			l = '\n'.join((l, ' '.join(map(str, self.lazy[cnt:cnt + (1 << i)]))))
			cnt += 1 << i
		return '\n'.join((s, l))

	def _ascend(self, k):
		k = k >> 1
		c = k.bit_length()
		for j in range(c):
			idx = k >> j
			self.data[idx] = self.fx(self.data[2 * idx], self.data[2 * idx + 1])

	def _descend(self, k):
		k = k >> 1
		idx = 1
		c = k.bit_length()
		for j in range(1, c + 1):
			idx = k >> c - j
			if self.lazy[idx] == self.em:
				continue
			self.data[2 * idx] = self.fa(self.lazy[idx], 2 * idx)
			self.data[2 * idx + 1] = self.fa(self.lazy[idx], 2 * idx + 1)
			self.lazy[2 * idx] = self.fm(self.lazy[idx], self.lazy[2 * idx])
			self.lazy[2 * idx + 1] = self.fm(self.lazy[idx], self.lazy[2 * idx + 1])
			self.lazy[idx] = self.em

	def query(self, l, r):
		L = l + self.N0
		R = r + self.N0
		self._descend(L // (L & -L))
		self._descend(R // (R & -R) - 1)
		sl = self.ex
		sr = self.ex
		while L < R:
			if R & 1:
				R -= 1
				sr = self.fx(self.data[R], sr)
			if L & 1:
				sl = self.fx(sl, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return self.fx(sl, sr)

	def operate(self, l, r, x):
		L = l + self.N0
		R = r + self.N0
		Li = L // (L & -L)
		Ri = R // (R & -R)
		self._descend(Li)
		self._descend(Ri - 1)
		while L < R:
			if R & 1:
				R -= 1
				self.data[R] = self.fa(x, R)
				self.lazy[R] = self.fm(x, self.lazy[R])
			if L & 1:
				self.data[L] = self.fa(x, L)
				self.lazy[L] = self.fm(x, self.lazy[L])
				L += 1
			L >>= 1
			R >>= 1
		self._ascend(Li)
		self._ascend(Ri - 1)
MOD = 998244353
mask = (1 << 32) - 1
(N, Q) = map(int, readline().split())
A = list(map(int, readline().split()))
A = [(0, 1, 0) if a == 1 else (1, 0, 0) for a in A]
T = Lazysegtree(A, None, (0, 0, 0), xor, 0, None, initialize=True)
Ans = []
for _ in range(Q):
	(t, *s) = readline().split()
	if t == '1':
		(l, r) = map(int, s)
		T.operate(l - 1, r, 1)
	else:
		(l, r) = map(int, s)
		Ans.append(T.query(l - 1, r)[2])
print('\n'.join(map(str, Ans)))


from typing import Callable, List, TypeVar
S = TypeVar('S')
F = TypeVar('F')

class LazySegmentTree:
	__slots__ = ['e', 'op', 'id', 'mapping', 'composition', '_n', '_log', '_size', 'tree', 'lazy']

	def __init__(self, a: List[S], e: S, op: Callable[[S, S], S], id_: F, mapping: Callable[[F, S], S], composition: Callable[[F, F], F]) -> None:
		self.e = e
		self.op = op
		self.id = id_
		self.mapping = mapping
		self.composition = composition
		self._n = len(a)
		self._log = (self._n - 1).bit_length()
		self._size = 1 << self._log
		self.tree = [e] * self._size + a + [e] * (self._size - self._n)
		for i in range(self._size - 1, 0, -1):
			self._update(i)
		self.lazy = [id_] * self._size

	def _update(self, k: int) -> None:
		self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

	def _apply_all(self, k: int, f: F) -> None:
		self.tree[k] = self.mapping(f, self.tree[k])
		if k < self._size:
			self.lazy[k] = self.composition(f, self.lazy[k])

	def _push(self, k: int) -> None:
		self._apply_all(2 * k, self.lazy[k])
		self._apply_all(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.id

	def set(self, k: int, x: S) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = x
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def get(self, k: int) -> S:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		return self.tree[k]

	def prod(self, l: int, r: int) -> S:
		assert 0 <= l <= r <= self._n
		if l == r:
			return self.e
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r >> i)
		(sml, smr) = (self.e, self.e)
		while l < r:
			if l & 1:
				sml = self.op(sml, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.tree[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def prod_all(self) -> S:
		return self.tree[1]

	def apply(self, k: int, f: F) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = self.mapping(f, self.tree[k])
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def apply_range(self, l: int, r: int, f: F) -> None:
		assert 0 <= l <= r <= self._n
		if l == r:
			return
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r - 1 >> i)
		(l_tmp, r_tmp) = (l, r)
		while l < r:
			if l & 1:
				self._apply_all(l, f)
				l += 1
			if r & 1:
				r -= 1
				self._apply_all(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l_tmp, r_tmp)
		for i in range(1, self._log + 1):
			if l >> i << i != l:
				self._update(l >> i)
			if r >> i << i != r:
				self._update(r - 1 >> i)

	def max_right(self, l: int, g: Callable[[S], bool]) -> int:
		assert 0 <= l <= self._n
		assert g(self.e)
		if l == self._n:
			return self._n
		l += self._size
		for i in range(self._log, 0, -1):
			self._push(l >> i)
		sm = self.e
		while True:
			while not l & 1:
				l >>= 1
			if not g(self.op(sm, self.tree[l])):
				while l < self._size:
					l *= 2
					if g(self.op(sm, self.tree[l])):
						sm = self.op(sm, self.tree[l])
						l += 1
				return l - self._size
			sm = self.op(sm, self.tree[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g: Callable[[S], bool]) -> int:
		assert 0 <= r <= self._n
		assert g(self.e)
		if not r:
			return 0
		r += self._size
		for i in range(self._log, 0, -1):
			self._push(r - 1 >> i)
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not g(self.op(self.tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if g(self.op(self.tree[r], sm)):
						sm = self.op(self.tree[r], sm)
						r -= 1
				return r + 1 - self._size
			sm = self.op(self.tree[r], sm)
			if r & -r == r:
				break
		return 0
import sys
from operator import xor
readline = sys.stdin.buffer.readline
(N, Q) = map(int, readline().split())
(*A,) = map(int, readline().split())
dic = {0: (1, 0, 0), 1: (0, 1, 0)}
tree = LazySegmentTree([dic[a] for a in A], e=(0, 0, 0), op=lambda m1, m2: (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0]), id_=0, mapping=lambda o, m: (m[1], m[0], m[0] * m[1] - m[2]) if o else m, composition=xor)
res = []
for _ in range(Q):
	(t, l, r) = map(int, readline().split())
	if t == 1:
		tree.apply_range(l - 1, r, 1)
	else:
		res.append(tree.prod(l - 1, r)[2])
print('\n'.join(map(str, res)))


def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():

	class LazySegmentTree:
		__slots__ = ['n', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

		def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
			self.me = monoid_identity
			self.oe = operator_identity
			self.fmm = func_monoid_monoid
			self.fmo = func_monoid_operator
			self.foo = func_operator_operator
			self.n = len(monoid_data)
			self.data = monoid_data * 2
			for i in range(self.n - 1, 0, -1):
				self.data[i] = self.fmm(self.data[2 * i], self.data[2 * i + 1])
			self.lazy = [self.oe] * (self.n * 2)

		def update(self, index, value):
			index += self.n
			for shift in range(index.bit_length() - 1, 0, -1):
				i = index >> shift
				self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
				self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
				self.data[i] = self.fmo(self.data[i], self.lazy[i])
				self.lazy[i] = self.oe
			self.data[index] = value
			self.lazy[index] = self.oe
			i = index
			while i > 1:
				i //= 2
				self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
				self.lazy[i] = self.oe

		def range_update(self, l, r, operator):
			l += self.n
			r += self.n
			indices = []
			l0 = l // (l & -l) // 2
			r0 = (r // (r & -r) - 1) // 2
			while r0 > l0:
				indices.append(r0)
				r0 //= 2
			while l0 > r0:
				indices.append(l0)
				l0 //= 2
			while l0 and l0 != r0:
				indices.append(r0)
				r0 //= 2
				if l0 == r0:
					break
				indices.append(l0)
				l0 //= 2
			while r0:
				indices.append(r0)
				r0 //= 2
			for i in reversed(indices):
				self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
				self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
				self.data[i] = self.fmo(self.data[i], self.lazy[i])
				self.lazy[i] = self.oe
			while l < r:
				if l % 2:
					self.lazy[l] = self.foo(self.lazy[l], operator)
					l += 1
				if r % 2:
					r -= 1
					self.lazy[r] = self.foo(self.lazy[r], operator)
				l //= 2
				r //= 2
			for i in indices:
				self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
				self.lazy[i] = self.oe

		def query(self, l, r):
			l += self.n
			r += self.n
			indices = []
			l0 = l // (l & -l) // 2
			r0 = (r // (r & -r) - 1) // 2
			while r0 > l0:
				indices.append(r0)
				r0 //= 2
			while l0 > r0:
				indices.append(l0)
				l0 //= 2
			while l0 and l0 != r0:
				indices.append(r0)
				r0 //= 2
				if l0 == r0:
					break
				indices.append(l0)
				l0 //= 2
			while r0:
				indices.append(r0)
				r0 //= 2
			for i in reversed(indices):
				self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
				self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
				self.data[i] = self.fmo(self.data[i], self.lazy[i])
				self.lazy[i] = self.oe
			left_folded = self.me
			right_folded = self.me
			while l < r:
				if l % 2:
					left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
					l += 1
				if r % 2:
					r -= 1
					right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
				l //= 2
				r //= 2
			return self.fmm(left_folded, right_folded)
	(N, Q) = LI()
	A = LI()
	B = []
	for i in range(N):
		if A[i]:
			temp = (0, 1, 0)
		else:
			temp = (1, 0, 0)
		B.append(temp)

	def foo(x, y):
		return x ^ y

	def fmm(x, y):
		z1 = x[0] + y[0]
		z2 = x[1] + y[1]
		z3 = x[2] + y[2] + x[1] * y[0]
		return (z1, z2, z3)

	def fmo(x, y):
		if y:
			z1 = x[1]
			z2 = x[0]
			z3 = x[0] * x[1] - x[2]
			return (z1, z2, z3)
		else:
			return x
	seg = LazySegmentTree(B, (0, 0, 0), 0, fmm, fmo, foo)
	ans = []
	for _ in range(Q):
		(t, l, r) = MI()
		if t == 1:
			seg.range_update(l - 1, r, 1)
		else:
			temp = seg.query(l - 1, r)
			ans.append(temp[-1])
	for v in ans:
		print(v)
main()


class LazySegmentTree:
	__slots__ = ['n', 'original_size', 'log', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

	def __init__(self, length_or_list, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
		self.me = monoid_identity
		self.oe = operator_identity
		self.fmm = func_monoid_monoid
		self.fmo = func_monoid_operator
		self.foo = func_operator_operator
		if isinstance(length_or_list, int):
			self.original_size = length_or_list
			self.log = (self.original_size - 1).bit_length()
			self.n = 1 << self.log
			self.data = [self.me] * (self.n * 2)
			self.lazy = [self.oe] * (self.n * 2)
		elif isinstance(length_or_list, list):
			self.original_size = len(length_or_list)
			self.log = (self.original_size - 1).bit_length()
			self.n = 1 << self.log
			self.data = [self.me] * self.n + length_or_list + [self.me] * (self.n - self.original_size)
			for i in range(self.n - 1, 0, -1):
				self.data[i] = self.fmm(self.data[2 * i], self.data[2 * i + 1])
			self.lazy = [self.oe] * (self.n * 2)
		else:
			raise TypeError(f"The argument 'length_or_list' must be an integer or a list, not {type(length_or_list).__name__}")

	def replace(self, index, value):
		index += self.n
		for shift in range(self.log, 0, -1):
			i = index >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		self.data[index] = value
		self.lazy[index] = self.oe
		i = index
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def __getitem__(self, index):
		index += self.n
		for shift in range(self.log, 0, -1):
			i = index >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		return self.data[index]

	def effect(self, l, r, operator):
		if l == r:
			return
		l += self.n
		r += self.n
		l0 = l
		r0 = r - 1
		while l0 % 2 == 0:
			l0 //= 2
		while r0 % 2 == 1:
			r0 //= 2
		for shift in range(self.log, 0, -1):
			i = l >> shift
			if i << shift != l:
				self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
				self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
				self.data[i] = self.fmo(self.data[i], self.lazy[i])
				self.lazy[i] = self.oe
			i = r >> shift
			if i << shift != r:
				self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
				self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
				self.data[i] = self.fmo(self.data[i], self.lazy[i])
				self.lazy[i] = self.oe
		while l < r:
			if l % 2:
				self.lazy[l] = self.foo(self.lazy[l], operator)
				l += 1
			if r % 2:
				r -= 1
				self.lazy[r] = self.foo(self.lazy[r], operator)
			l //= 2
			r //= 2
		i = l0
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe
		i = r0
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def folded(self, l, r):
		l += self.n
		r += self.n
		for shift in range(self.log, 0, -1):
			i = l >> shift
			if i << shift != l:
				self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
				self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
				self.data[i] = self.fmo(self.data[i], self.lazy[i])
				self.lazy[i] = self.oe
			i = r >> shift
			if i << shift != r:
				self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
				self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
				self.data[i] = self.fmo(self.data[i], self.lazy[i])
				self.lazy[i] = self.oe
		left_folded = self.me
		right_folded = self.me
		while l < r:
			if l % 2:
				left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
			l //= 2
			r //= 2
		return self.fmm(left_folded, right_folded)

def atc2():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	monoid_data = [(0, 1, 0) if A == b'1' else (1, 0, 0) for A in input().split()]

	def fmm(m1, m2):
		return (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0])

	def fmo(m1, o1):
		if o1:
			return (m1[1], m1[0], m1[0] * m1[1] - m1[2])
		else:
			return m1

	def foo(o1, o2):
		return o1 ^ o2
	lst = LazySegmentTree(monoid_data, (0, 0, 0), 0, fmm, fmo, foo)
	ans = []
	for _ in range(Q):
		(T, L, R) = map(int, input().split())
		if T == 1:
			lst.effect(L - 1, R, 1)
		else:
			ans.append(lst.folded(L - 1, R)[2])
	print('\n'.join(map(str, ans)))
atc2()


class LazySegmentTree:

	def __init__(self, n, f, default=(0, 0, 1)):
		self.num_leaf = 2 ** (n - 1).bit_length()
		self.data = [default] * (2 * self.num_leaf)
		self.lazy = [True] * (2 * self.num_leaf)
		self.f = f

	def first_update(self, i, x):
		i += self.num_leaf
		self.data[i] = x
		i >>= 1
		while i > 0:
			self.data[i] = self.f(self.data[2 * i], self.data[2 * i + 1])
			i >>= 1

	def gindex(self, l, r):
		lis = []
		l += self.num_leaf
		r += self.num_leaf
		lm = l // (l & -l) >> 1
		rm = r // (r & -r) >> 1
		while l < r:
			if l <= lm:
				lis.append(l)
			if r <= rm:
				lis.append(r)
			l >>= 1
			r >>= 1
		while l:
			lis.append(l)
			l >>= 1
		lis.reverse()
		return lis

	def lazy_processing(self, i):
		self.data[i] = (self.data[i][1] * self.data[i][2] - self.data[i][0], self.data[i][2], self.data[i][1])
		self.lazy[i] = not self.lazy[i]

	def propagate(self, lis):
		for i in lis:
			if self.lazy[i]:
				continue
			self.lazy_processing(2 * i)
			self.lazy_processing(2 * i + 1)
			self.lazy[i] = True

	def update(self, l, r):
		lis = self.gindex(l, r)
		self.propagate(lis)
		l += self.num_leaf
		r += self.num_leaf - 1
		while l < r:
			if l & 1:
				self.lazy_processing(l)
				l += 1
			if not r & 1:
				self.lazy_processing(r)
				r -= 1
			l >>= 1
			r >>= 1
		if l == r:
			self.lazy_processing(l)
		lis.reverse()
		for i in lis:
			self.data[i] = self.f(self.data[2 * i], self.data[2 * i + 1])

	def query(self, l, r):
		self.propagate(self.gindex(l, r))
		l += self.num_leaf
		r += self.num_leaf - 1
		(lres, rres) = ((0, 1, 0), self.data[0])
		while l < r:
			if l & 1:
				lres = self.f(lres, self.data[l])
				l += 1
			if not r & 1:
				rres = self.f(self.data[r], rres)
				r -= 1
			l >>= 1
			r >>= 1
		if l == r:
			res = self.f(self.f(lres, self.data[l]), rres)
		else:
			res = self.f(lres, rres)
		return res
from sys import stdin
input = stdin.buffer.readline

def main():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))

	def f(tup1, tup2):
		return (tup1[0] + tup2[0] + tup1[2] * tup2[1], tup1[1] + tup2[1], tup1[2] + tup2[2])
	lst = LazySegmentTree(n, f=f)
	for (i, x) in enumerate(a):
		lst.first_update(i, (0, 1 - x, x))
	ans = []
	for _ in range(q):
		(t, l, r) = list(map(int, input().split()))
		if t == 1:
			lst.update(l - 1, r)
		else:
			ans.append(lst.query(l - 1, r)[0])
	for i in ans:
		print(i)
main()


from operator import xor
from typing import Callable, List, TypeVar
S = TypeVar('S')
F = TypeVar('F')

class LazySegmentTree:
	__slots__ = ['e', 'op', 'id', 'mapping', 'composition', '_n', '_log', '_size', 'tree', 'lazy']

	def __init__(self, a: List[S], e: S, op: Callable[[S, S], S], id_: F, mapping: Callable[[F, S], S], composition: Callable[[F, F], F]) -> None:
		self.e = e
		self.op = op
		self.id = id_
		self.mapping = mapping
		self.composition = composition
		self._n = len(a)
		self._log = (self._n - 1).bit_length()
		self._size = 1 << self._log
		self.tree = [e] * self._size + a + [e] * (self._size - self._n)
		for i in range(self._size - 1, 0, -1):
			self._update(i)
		self.lazy = [id_] * self._size

	def _update(self, k: int) -> None:
		self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

	def _apply_all(self, k: int, f: F) -> None:
		self.tree[k] = self.mapping(f, self.tree[k])
		if k < self._size:
			self.lazy[k] = self.composition(f, self.lazy[k])

	def _push(self, k: int) -> None:
		self._apply_all(2 * k, self.lazy[k])
		self._apply_all(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.id

	def set(self, k: int, x: S) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = x
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def get(self, k: int) -> S:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		return self.tree[k]

	def prod(self, l: int, r: int) -> S:
		assert 0 <= l <= r <= self._n
		if l == r:
			return self.e
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r >> i)
		(sml, smr) = (self.e, self.e)
		while l < r:
			if l & 1:
				sml = self.op(sml, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.tree[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def prod_all(self) -> S:
		return self.tree[1]

	def apply(self, k: int, f: F) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = self.mapping(f, self.tree[k])
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def apply_range(self, l: int, r: int, f: F) -> None:
		assert 0 <= l <= r <= self._n
		if l == r:
			return
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r - 1 >> i)
		(l_tmp, r_tmp) = (l, r)
		while l < r:
			if l & 1:
				self._apply_all(l, f)
				l += 1
			if r & 1:
				r -= 1
				self._apply_all(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l_tmp, r_tmp)
		for i in range(1, self._log + 1):
			if l >> i << i != l:
				self._update(l >> i)
			if r >> i << i != r:
				self._update(r - 1 >> i)

	def max_right(self, l: int, g: Callable[[S], bool]) -> int:
		assert 0 <= l <= self._n
		assert g(self.e)
		if l == self._n:
			return self._n
		l += self._size
		for i in range(self._log, 0, -1):
			self._push(l >> i)
		sm = self.e
		while True:
			while not l & 1:
				l >>= 1
			if not g(self.op(sm, self.tree[l])):
				while l < self._size:
					l *= 2
					if g(self.op(sm, self.tree[l])):
						sm = self.op(sm, self.tree[l])
						l += 1
				return l - self._size
			sm = self.op(sm, self.tree[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g: Callable[[S], bool]) -> int:
		assert 0 <= r <= self._n
		assert g(self.e)
		if not r:
			return 0
		r += self._size
		for i in range(self._log, 0, -1):
			self._push(r - 1 >> i)
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not g(self.op(self.tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if g(self.op(self.tree[r], sm)):
						sm = self.op(self.tree[r], sm)
						r -= 1
				return r + 1 - self._size
			sm = self.op(self.tree[r], sm)
			if r & -r == r:
				break
		return 0

def op(l, r):
	return [l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0]]

def mapping(f, x):
	if not f:
		return x
	return [x[1], x[0], x[0] * x[1] - x[2]]
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
dic = {0: [1, 0, 0], 1: [0, 1, 0]}
lst = LazySegmentTree([dic[v] for v in A], [0, 0, 0], op, False, mapping, xor)
for i in range(Q):
	(T, L, R) = map(int, input().split())
	if T == 1:
		lst.apply_range(L - 1, R, True)
	else:
		print(lst.prod(L - 1, R)[2])


class LazySegmentTree:

	def __init__(self, op_X, e_X, mapping, compose, id_M, N, array=None):
		self.e_X = e_X
		self.op_X = op_X
		self.mapping = mapping
		self.compose = compose
		self.id_M = id_M
		self.N = N
		self.log = (N - 1).bit_length()
		self.N0 = 1 << self.log
		self.data = [e_X] * (2 * self.N0)
		self.lazy = [id_M] * self.N0
		if array:
			assert N == len(array)
			self.data[self.N0:self.N0 + self.N] = array
			for i in range(self.N0 - 1, 0, -1):
				self.update(i)

	def point_set(self, p, x):
		p += self.N0
		for i in range(self.log, 0, -1):
			self.push(p >> i)
		self.data[p] = x
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def point_get(self, p):
		p += self.N0
		for i in range(self.log, 0, -1):
			self.push(p >> i)
		return self.data[p]

	def prod(self, l, r):
		if l == r:
			return self.e_X
		l += self.N0
		r += self.N0
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r >> i)
		sml = smr = self.e_X
		while l < r:
			if l & 1:
				sml = self.op_X(sml, self.data[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op_X(self.data[r], smr)
			l >>= 1
			r >>= 1
		return self.op_X(sml, smr)

	def all_prod(s):
		return self.data[1]

	def apply(self, p, f):
		p += self.N0
		for i in range(self.log, 0, -1):
			self.push(p >> i)
		self.data[p] = self.mapping(f, self.data[p])
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def apply(self, l, r, f):
		if l == r:
			return
		l += self.N0
		r += self.N0
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.update(l >> i)
			if r >> i << i != r:
				self.update(r - 1 >> i)

	def max_right(self, l, g):
		if l == self.N:
			return self.N
		l += self.N0
		for i in range(self.log, 0, -1):
			self.push(l >> i)
		sm = self.e_X
		while True:
			while l & 1 == 0:
				l >>= 1
			if not g(self.op_X(sm, self.data[l])):
				while l < self.N0:
					self.push(l)
					l *= 2
					if g(self.op_X(sm, self.data[l])):
						sm = self.op_X(sm, self.data[l])
						l += 1
				return l - self.N0
			sm = self.op_X(sm, self.data[l])
			l += 1
			if l & -l == l:
				break
		return self.N

	def min_left(self, r, g):
		if r == 0:
			return 0
		r += self.N0
		for i in range(self.log, 0, -1):
			self.push(r - 1 >> i)
		sm = self.e_X
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not g(self.op_X(self.data[r], sm)):
				while r < self.N0:
					self.push(r)
					r = 2 * r + 1
					if g(self.op_X(self.data[r], sm)):
						sm = self.op_X(self.data[r], sm)
						r -= 1
				return r + 1 - self.N0
			sm = self.op_X(self.data[r], sm)
			if r & -r == r:
				break
		return 0

	def update(self, k):
		self.data[k] = self.op_X(self.data[2 * k], self.data[2 * k + 1])

	def all_apply(self, k, f):
		self.data[k] = self.mapping(f, self.data[k])
		if k < self.N0:
			self.lazy[k] = self.compose(f, self.lazy[k])

	def push(self, k):
		if self.lazy[k] == self.id_M:
			return
		self.data[2 * k] = self.mapping(self.lazy[k], self.data[2 * k])
		self.data[2 * k + 1] = self.mapping(self.lazy[k], self.data[2 * k + 1])
		if 2 * k < self.N0:
			self.lazy[2 * k] = self.compose(self.lazy[k], self.lazy[2 * k])
			self.lazy[2 * k + 1] = self.compose(self.lazy[k], self.lazy[2 * k + 1])
		self.lazy[k] = self.id_M
e_X = (0, 0, 0, 0)
id_M = 0

def op_X(X, Y):
	(x, y, p, q) = X
	(z, w, r, s) = Y
	return (x + z, y + w, p + r + x * w, q + s + y * z)
from operator import xor
compose = xor

def mapping(f, X):
	if f:
		(x, y, p, q) = X
		return (y, x, q, p)
	else:
		return X
import sys
readline = sys.stdin.readline
(n, q) = map(int, readline().split())
(*a,) = map(int, readline().split())
seg = LazySegmentTree(op_X, e_X, mapping, compose, id_M, n, array=[(1 - ai, ai, 0, 0) for ai in a])
for _ in range(q):
	(t, l, r) = map(int, readline().split())
	l -= 1
	if t == 1:
		seg.apply(l, r, 1)
	else:
		print(seg.prod(l, r)[-1])


from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify
import itertools
import math, fractions
import sys, copy

def L():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline().rstrip())

def SL():
	return list(sys.stdin.readline().rstrip())

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI1():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def R(n):
	return [sys.stdin.readline().strip() for _ in range(n)]

def LR(n):
	return [L() for _ in range(n)]

def IR(n):
	return [I() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def LIR1(n):
	return [LI1() for _ in range(n)]

def SR(n):
	return [SL() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]

def perm(n, r):
	return math.factorial(n) // math.factorial(r)

def comb(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

def make_list(n, *args, default=0):
	return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = 'abcdefghijklmnopqrstuvwxyz'
ALPHABETS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
MOD = 1000000007
INF = float('inf')
sys.setrecursionlimit(1000000)

class LazySegmentTree:

	def __init__(self, initial_values, monoid_func, composition, effect, monoid_identity, operator_identity):
		self.N = len(initial_values)
		self.monoid_func = monoid_func
		self.composition = composition
		self.effect = effect
		self.monoid_identity = monoid_identity
		self.operator_identity = operator_identity
		self.data = [self.monoid_identity] * (2 * self.N)
		self.lazy = [self.operator_identity] * (2 * self.N)
		self.size = [0] * (2 * self.N)
		for (i, ai) in enumerate(initial_values):
			self.data[self.N + i] = ai
			self.size[self.N + i] = 1
		for i in range(self.N - 1, 0, -1):
			self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
			self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

	def update(self, i, x):
		i += self.N
		self.data[i] = x
		while i > 1:
			i >>= 1
			self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])

	def eval_at(self, i):
		return self.effect(self.data[i], self.lazy[i], self.size[i])

	def eval_above(self, i):
		while i > 1:
			i >>= 1
			self.data[i] = self.monoid_func(self.eval_at(i << 1), self.eval_at(i << 1 | 1))

	def propagate_at(self, i):
		self.data[i] = self.effect(self.data[i], self.lazy[i], self.size[i])
		self.lazy[i << 1] = self.composition(self.lazy[i << 1], self.lazy[i])
		self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
		self.lazy[i] = self.operator_identity

	def propagate_above(self, i):
		H = i.bit_length()
		for h in range(H, 0, -1):
			self.propagate_at(i >> h)

	def fold(self, L, R):
		L += self.N
		R += self.N
		L0 = L // (L & -L)
		R0 = R // (R & -R) - 1
		self.propagate_above(L0)
		self.propagate_above(R0)
		vL = self.monoid_identity
		vR = self.monoid_identity
		while L < R:
			if L & 1:
				vL = self.monoid_func(vL, self.eval_at(L))
				L += 1
			if R & 1:
				R -= 1
				vR = self.monoid_func(self.eval_at(R), vR)
			L >>= 1
			R >>= 1
		return self.monoid_func(vL, vR)

	def apply_range(self, L, R, x):
		L += self.N
		R += self.N
		L0 = L // (L & -L)
		R0 = R // (R & -R) - 1
		self.propagate_above(L0)
		self.propagate_above(R0)
		while L < R:
			if L & 1:
				self.lazy[L] = self.composition(self.lazy[L], x)
				L += 1
			if R & 1:
				R -= 1
				self.lazy[R] = self.composition(self.lazy[R], x)
			L >>= 1
			R >>= 1
		self.eval_above(L0)
		self.eval_above(R0)

def main():
	(N, Q) = LI()
	A = LI()
	X = [(1 - a, a, 0) for a in A]
	query = LIR(Q)
	monoid_identity = (0, 0, 0)
	operator_identity = 0

	def monoid_func(x, y):
		return (x[0] + y[0], x[1] + y[1], x[2] + y[2] + x[1] * y[0])

	def composition(f, g):
		return f ^ g

	def effect(x, f, r):
		(c0, c1, cnt) = x
		return (c1, c0, c0 * c1 - cnt) if f else x
	seg = LazySegmentTree(X, monoid_func, composition, effect, monoid_identity, operator_identity)
	for (t, l, r) in query:
		if t == 1:
			seg.apply_range(l - 1, r, 1)
		else:
			print(seg.fold(l - 1, r)[-1])
main()


class LazySegmentTree:

	def __init__(self, n, init, merge, merge_unit, operate, merge_operate, operate_unit):
		self.merge = merge
		self.merge_unit = merge_unit
		self.operate = operate
		self.merge_operate = merge_operate
		self.operate_unit = operate_unit
		self.n = (n - 1).bit_length()
		self.num = 1 << self.n
		self.data = [merge_unit for i in range(1 << self.n + 1)]
		self.lazy = [operate_unit for i in range(1 << self.n + 1)]
		if init:
			for i in range(n):
				self.data[2 ** self.n + i] = init[i]
			for i in range(2 ** self.n - 1, 0, -1):
				self.data[i] = self.merge(self.data[2 * i], self.data[2 * i + 1])

	def propagate(self, v):
		ope = self.lazy[v]
		if ope == self.operate_unit:
			return
		self.lazy[v] = self.operate_unit
		self.data[2 * v] = self.operate(self.data[2 * v], ope)
		self.data[2 * v + 1] = self.operate(self.data[2 * v + 1], ope)
		self.lazy[2 * v] = self.merge_operate(self.lazy[2 * v], ope)
		self.lazy[2 * v + 1] = self.merge_operate(self.lazy[2 * v + 1], ope)

	def propagate_above(self, i):
		m = i.bit_length() - 1
		for bit in range(m, 0, -1):
			v = i >> bit
			self.propagate(v)

	def remerge_above(self, i):
		while i:
			i >>= 1
			self.data[i] = self.operate(self.merge(self.data[2 * i], self.data[2 * i + 1]), self.lazy[i])

	def update(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		while l < r:
			if l & 1:
				self.data[l] = self.operate(self.data[l], x)
				self.lazy[l] = self.merge_operate(self.lazy[l], x)
				l += 1
			if r & 1:
				self.data[r - 1] = self.operate(self.data[r - 1], x)
				self.lazy[r - 1] = self.merge_operate(self.lazy[r - 1], x)
			l >>= 1
			r >>= 1
		self.remerge_above(l0)
		self.remerge_above(r0)

	def query(self, l, r):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		res = self.merge_unit
		L = []
		R = []
		while l < r:
			if l & 1:
				L.append(l)
				l += 1
			if r & 1:
				R.append(r - 1)
			l >>= 1
			r >>= 1
		if L and R and (R[-1] == L[-1]):
			R.pop()
		R = R[::-1]
		m = L + R
		for idx in m:
			res = self.merge(res, self.data[idx])
		return res

	def bisect_l(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.data[l][0] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.data[r - 1][0] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		res = -1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			res = pos - self.num
		if Rmin != -1:
			pos = Rmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			if res == -1:
				res = pos - self.num
			else:
				res = min(res, pos - self.num)
		return res
import sys
input = sys.stdin.readline
merge = lambda x, y: (x[0] + y[0] + x[2] * y[1], x[1] + y[1], x[2] + y[2])
merge_unit = (0, 0, 0)

def operate(x, y):
	if y:
		return (x[1] * x[2] - x[0], x[2], x[1])
	else:
		return x
merge_operate = lambda x, y: (x + y) % 2
operate_unit = 0
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
	if A[i] == 0:
		A[i] = (0, 1, 0)
	else:
		A[i] = (0, 0, 1)
LST = LazySegmentTree(N, A, merge, merge_unit, operate, merge_operate, operate_unit)
for i in range(Q):
	(t, l, r) = map(int, input().split())
	l = l - 1
	if t == 1:
		LST.update(l, r, 1)
	else:
		print(LST.query(l, r)[0])


MOD = 998244353
mask32 = (1 << 32) - 1
mask20 = (1 << 20) - 1
mask40 = (1 << 40) - 1

class LazySegmentTree:
	__slots__ = ['n', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

	def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
		self.me = monoid_identity
		self.oe = operator_identity
		self.fmm = func_monoid_monoid
		self.fmo = func_monoid_operator
		self.foo = func_operator_operator
		self.n = len(monoid_data)
		self.data = monoid_data * 2
		for i in range(self.n - 1, 0, -1):
			self.data[i] = self.fmm(self.data[2 * i], self.data[2 * i + 1])
		self.lazy = [self.oe] * (self.n * 2)

	def replace(self, index, value):
		index += self.n
		for shift in range(index.bit_length() - 1, 0, -1):
			i = index >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		self.data[index] = value
		self.lazy[index] = self.oe
		i = index
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def effect(self, l, r, operator):
		l += self.n
		r += self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		for shift in range(l0.bit_length() - 1, 0, -1):
			i = l0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		for shift in range(r0.bit_length() - 1, 0, -1):
			i = r0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		while l < r:
			if l % 2:
				self.lazy[l] = self.foo(self.lazy[l], operator)
				l += 1
			if r % 2:
				r -= 1
				self.lazy[r] = self.foo(self.lazy[r], operator)
			l //= 2
			r //= 2
		i = l0
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe
		i = r0
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def folded(self, l, r):
		l += self.n
		r += self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		for shift in range(l0.bit_length() - 1, 0, -1):
			i = l0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		for shift in range(r0.bit_length() - 1, 0, -1):
			i = r0 >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		left_folded = self.me
		right_folded = self.me
		while l < r:
			if l % 2:
				left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
			l //= 2
			r //= 2
		return self.fmm(left_folded, right_folded)

def yosupo():
	import sys
	input = sys.stdin.buffer.readline

	def fmm(m1, m2):
		m = m1 + m2
		return ((m >> 32) % MOD << 32) + (m & mask32)

	def fmo(m1, o1):
		val = m1 >> 32
		cnt = m1 & mask32
		b = o1 >> 32
		c = o1 & mask32
		return ((b * val + c * cnt) % MOD << 32) + cnt

	def foo(o1, o2):
		b1 = o1 >> 32
		c1 = o1 & mask32
		b2 = o2 >> 32
		c2 = o2 & mask32
		b = b1 * b2 % MOD
		c = (c1 * b2 + c2) % MOD
		return (b << 32) + c
	(N, Q) = map(int, input().split())
	monoid_data = [(A << 32) + 1 for A in map(int, input().split())]
	lst = LazySegmentTree(monoid_data, 1, 1 << 32, fmm, fmo, foo)
	for _ in range(Q):
		(q, *k) = map(int, input().split())
		if q == 0:
			o = (k[2] << 32) + k[3]
			lst.effect(k[0], k[1], o)
		else:
			print(lst.folded(k[0], k[1]) >> 32)

def test():
	import random

	def madd(a, b):
		return (a + b) % MOD

	def mmul(a, b):
		return a * b % MOD
	lst = LazySegmentTree([0] * 10, 0, 1, madd, mmul, mmul)
	ls = [0] * 10
	for _ in range(10000000):
		if random.randint(0, 1):
			l = random.randint(0, 9)
			r = random.randint(l + 1, 10)
			e = random.randint(1, 782)
			lst.effect(l, r, e)
			for i in range(l, r):
				ls[i] *= e
				ls[i] %= MOD
		else:
			l = random.randint(0, 9)
			r = random.randint(l + 1, 10)
			if lst.folded(l, r) != sum(ls[l:r]):
				print(ls)
				print(l, r)
				print(lst.folded(l, r))

def ruq():
	import sys
	input = sys.stdin.buffer.readline

	def f(m1, m2):
		if m2 == -1:
			return m1
		else:
			return m2
	(N, Q) = map(int, input().split())
	monoid_data = [2147483647] * N
	lst = LazySegmentTree(monoid_data, -1, -1, f, f, f)
	for _ in range(Q):
		(q, *k) = map(int, input().split())
		if q == 0:
			lst.effect(k[0], k[1] + 1, k[2])
		else:
			print(lst.folded(k[0], k[0] + 1))

def atc():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	monoid_data = [1099511627776 if A == b'1' else 1152921504606846976 for A in input().split()]

	def fmm(m1, m2):
		return m1 + m2 + (m1 >> 40 & mask20) * (m2 >> 60)

	def fmo(m1, o1):
		if o1:
			cnt = m1 & mask40
			c1 = m1 >> 40 & mask20
			c0 = m1 >> 60
			return (c1 << 60) + (c0 << 40) + (c0 * c1 - cnt)
		else:
			return m1

	def foo(o1, o2):
		return o1 ^ o2
	lst = LazySegmentTree(monoid_data, 0, 0, fmm, fmo, foo)
	for _ in range(Q):
		(T, L, R) = map(int, input().split())
		if T == 1:
			lst.effect(L - 1, R, 1)
		else:
			print(lst.folded(L - 1, R) & mask40)

def test2():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	As = list(map(int, input().split()))
	monoid_data = [1099511627776 if A else 1152921504606846976 for A in As]

	def fmm(m1, m2):
		return m1 + m2 + (m1 >> 40 & mask20) * (m2 >> 60)

	def fmo(m1, o1):
		if o1:
			cnt = m1 & mask40
			c1 = m1 >> 40 & mask20
			c0 = m1 >> 60
			return (c1 << 60) + (c0 << 40) + (c0 * c1 - cnt)
		else:
			return m1

	def foo(o1, o2):
		return o1 ^ o2
	lst = LazySegmentTree(monoid_data, 0, 0, fmm, fmo, foo)
	for _ in range(Q):
		(T, L, R) = map(int, input().split())
		if T == 1:
			lst.effect(L - 1, R, 1)
			for i in range(L - 1, R):
				As[i] ^= 1
		else:
			print(As)
			cnt = 0
			for i in range(L - 1, R):
				for j in range(i + 1, R):
					cnt += As[i] * (As[j] ^ 1)
			if cnt != lst.folded(L - 1, R) & mask40:
				print('WA!')
				print(As[L - 1:R])
				print(lst.folded(L - 1, R) & mask40, cnt)
atc()


import sys
input = sys.stdin.readline

class Lazysegtree:

	def __init__(self, A, fx, ex, fm, em, fa, initialize=True):
		self.n = len(A)
		self.n0 = 2 ** (self.n - 1).bit_length()
		self.fm = fm
		self.ex = ex
		self.em = em
		self.lazy = [em] * (2 * self.n0)
		if initialize:
			self.data = [self.ex] * self.n0 + A + [self.ex] * (self.n0 - self.n)
			for i in range(self.n0 - 1, -1, -1):
				self.data[i] = self.fx(self.data[i * 2], self.data[i * 2 + 1])
		else:
			self.data = [self.ex] * (2 * self.n0)

	def fx(self, x, y):
		return (x[0] + y[0], x[1] + y[1], x[2] + y[2] + x[1] * y[0])

	def fa(self, ope, idx):
		if ope == 0:
			return self.data[idx]
		(zero, one, t) = self.data[idx]
		return (one, zero, (one + zero) * (one + zero - 1) // 2 - one * (one - 1) // 2 - zero * (zero - 1) // 2 - t)

	def _ascend(self, k):
		k = k >> 1
		c = k.bit_length()
		for j in range(c):
			idx = k >> j
			self.data[idx] = self.fx(self.data[2 * idx], self.data[2 * idx + 1])

	def _descend(self, k):
		k = k >> 1
		idx = 1
		c = k.bit_length()
		for j in range(1, c + 1):
			idx = k >> c - j
			if self.lazy[idx] == self.em:
				continue
			self.data[2 * idx] = self.fa(self.lazy[idx], 2 * idx)
			self.data[2 * idx + 1] = self.fa(self.lazy[idx], 2 * idx + 1)
			self.lazy[2 * idx] = self.fm(self.lazy[idx], self.lazy[2 * idx])
			self.lazy[2 * idx + 1] = self.fm(self.lazy[idx], self.lazy[2 * idx + 1])
			self.lazy[idx] = self.em

	def query(self, l, r):
		L = l + self.n0
		R = r + self.n0
		self._descend(L // (L & -L))
		self._descend(R // (R & -R) - 1)
		sl = self.ex
		sr = self.ex
		while L < R:
			if R & 1:
				R -= 1
				sr = self.fx(self.data[R], sr)
			if L & 1:
				sl = self.fx(sl, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return self.fx(sl, sr)

	def operate(self, l, r, x):
		L = l + self.n0
		R = r + self.n0
		Li = L // (L & -L)
		Ri = R // (R & -R)
		self._descend(Li)
		self._descend(Ri - 1)
		while L < R:
			if R & 1:
				R -= 1
				self.data[R] = self.fa(x, R)
				self.lazy[R] = self.fm(x, self.lazy[R])
			if L & 1:
				self.data[L] = self.fa(x, L)
				self.lazy[L] = self.fm(x, self.lazy[L])
				L += 1
			L >>= 1
			R >>= 1
		self._ascend(Li)
		self._ascend(Ri - 1)
(N, Q) = map(int, input().split())
(*A,) = map(int, input().split())
A = [(0, 1, 0) if a == 1 else (1, 0, 0) for a in A]
segtree = Lazysegtree(A, None, (0, 0, 0), lambda x, y: x ^ y, 0, None, initialize=True)
ans = []
for i in range(Q):
	(t, l, r) = map(int, input().split())
	if t == 1:
		segtree.operate(l - 1, r, 1)
	else:
		ans.append(segtree.query(l - 1, r)[2])
for i in range(len(ans)):
	print(ans[i])


MOD = 998244353
mask = (1 << 32) - 1
mask20 = (1 << 20) - 1
mask40 = (1 << 40) - 1

class LazySegmentTree:
	__slots__ = ['n', 'data', 'lazy', 'me', 'oe', 'fmm', 'fmo', 'foo']

	def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
		self.me = monoid_identity
		self.oe = operator_identity
		self.fmm = func_monoid_monoid
		self.fmo = func_monoid_operator
		self.foo = func_operator_operator
		self.n = len(monoid_data)
		self.data = monoid_data * 2
		for i in range(self.n - 1, 0, -1):
			self.data[i] = self.fmm(self.data[2 * i], self.data[2 * i + 1])
		self.lazy = [self.oe] * (self.n * 2)

	def replace(self, index, value):
		index += self.n
		for shift in range(index.bit_length() - 1, 0, -1):
			i = index >> shift
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		self.data[index] = value
		self.lazy[index] = self.oe
		i = index
		while i > 1:
			i //= 2
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def effect(self, l, r, operator):
		l += self.n
		r += self.n
		indices = []
		l0 = l
		r0 = r - 1
		while l0 % 2 == 0:
			l0 //= 2
		while r0 % 2 == 1:
			r0 //= 2
		l0 //= 2
		r0 //= 2
		while r0 > l0:
			indices.append(r0)
			r0 //= 2
		while l0 > r0:
			indices.append(l0)
			l0 //= 2
		while l0 and l0 != r0:
			indices.append(r0)
			r0 //= 2
			if l0 == r0:
				break
			indices.append(l0)
			l0 //= 2
		while r0:
			indices.append(r0)
			r0 //= 2
		for i in reversed(indices):
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		while l < r:
			if l % 2:
				self.lazy[l] = self.foo(self.lazy[l], operator)
				l += 1
			if r % 2:
				r -= 1
				self.lazy[r] = self.foo(self.lazy[r], operator)
			l //= 2
			r //= 2
		for i in indices:
			self.data[i] = self.fmm(self.fmo(self.data[2 * i], self.lazy[2 * i]), self.fmo(self.data[2 * i + 1], self.lazy[2 * i + 1]))
			self.lazy[i] = self.oe

	def folded(self, l, r):
		l += self.n
		r += self.n
		indices = []
		l0 = l
		r0 = r - 1
		while l0 % 2 == 0:
			l0 //= 2
		while r0 % 2 == 1:
			r0 //= 2
		l0 //= 2
		r0 //= 2
		while r0 > l0:
			indices.append(r0)
			r0 //= 2
		while l0 > r0:
			indices.append(l0)
			l0 //= 2
		while l0 and l0 != r0:
			indices.append(r0)
			r0 //= 2
			if l0 == r0:
				break
			indices.append(l0)
			l0 //= 2
		while r0:
			indices.append(r0)
			r0 //= 2
		for i in reversed(indices):
			self.lazy[2 * i] = self.foo(self.lazy[2 * i], self.lazy[i])
			self.lazy[2 * i + 1] = self.foo(self.lazy[2 * i + 1], self.lazy[i])
			self.data[i] = self.fmo(self.data[i], self.lazy[i])
			self.lazy[i] = self.oe
		left_folded = self.me
		right_folded = self.me
		while l < r:
			if l % 2:
				left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
			l //= 2
			r //= 2
		return self.fmm(left_folded, right_folded)

def main():
	import sys
	input = sys.stdin.buffer.readline

	def fmm(m1, m2):
		m = m1 + m2
		return ((m >> 32) % MOD << 32) + (m & mask)

	def fmo(m1, o1):
		val = m1 >> 32
		cnt = m1 & mask
		b = o1 >> 32
		c = o1 & mask
		return ((b * val + c * cnt) % MOD << 32) + cnt

	def foo(o1, o2):
		b1 = o1 >> 32
		c1 = o1 & mask
		b2 = o2 >> 32
		c2 = o2 & mask
		b = b1 * b2 % MOD
		c = (c1 * b2 + c2) % MOD
		return (b << 32) + c
	(N, Q) = map(int, input().split())
	monoid_data = [(A << 32) + 1 for A in map(int, input().split())]
	lst = LazySegmentTree(monoid_data, 1, 1 << 32, fmm, fmo, foo)
	for _ in range(Q):
		(q, *k) = map(int, input().split())
		if q == 0:
			o = (k[2] << 32) + k[3]
			lst.effect(k[0], k[1], o)
		else:
			print(lst.folded(k[0], k[1]) >> 32)

def test():
	import random

	def madd(a, b):
		return (a + b) % MOD

	def mmul(a, b):
		return a * b % MOD
	lst = LazySegmentTree([0] * 10, 0, 1, madd, mmul, mmul)
	ls = [0] * 10
	for _ in range(10000000):
		if random.randint(0, 1):
			l = random.randint(0, 9)
			r = random.randint(l + 1, 10)
			e = random.randint(1, 782)
			lst.effect(l, r, e)
			for i in range(l, r):
				ls[i] *= e
				ls[i] %= MOD
		else:
			l = random.randint(0, 9)
			r = random.randint(l + 1, 10)
			if lst.folded(l, r) != sum(ls[l:r]):
				print(ls)
				print(l, r)
				print(lst.folded(l, r))

def atc():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	monoid_data = [1099511627776 if A == b'1' else 1152921504606846976 for A in input().split()]

	def fmm(m1, m2):
		return m1 + m2 + (m1 >> 40 & mask20) * (m2 >> 60)

	def fmo(m1, o1):
		if o1:
			cnt = m1 & mask40
			c1 = m1 >> 40 & mask20
			c0 = m1 >> 60
			return (c1 << 60) + (c0 << 40) + (c0 * c1 - cnt)
		else:
			return m1

	def foo(o1, o2):
		return o1 ^ o2
	lst = LazySegmentTree(monoid_data, 0, 0, fmm, fmo, foo)
	for _ in range(Q):
		(T, L, R) = map(int, input().split())
		if T == 1:
			lst.effect(L - 1, R, 1)
		else:
			print(lst.folded(L - 1, R) & mask40)

def atc2():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	monoid_data = [(0, 1, 0) if A == b'1' else (1, 0, 0) for A in input().split()]

	def fmm(m1, m2):
		return (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0])

	def fmo(m1, o1):
		if o1:
			return (m1[1], m1[0], m1[0] * m1[1] - m1[2])
		else:
			return m1

	def foo(o1, o2):
		return o1 ^ o2
	lst = LazySegmentTree(monoid_data, (0, 0, 0), 0, fmm, fmo, foo)
	for _ in range(Q):
		(T, L, R) = map(int, input().split())
		if T == 1:
			lst.effect(L - 1, R, 1)
		else:
			print(lst.folded(L - 1, R)[2])

def mainbignum():
	import sys
	input = sys.stdin.buffer.readline
	bignum = 10 ** 9

	def fmm(m1, m2):
		m = m1 + m2
		(q, r) = divmod(m, bignum)
		return q % MOD * bignum + r

	def fmo(m1, o1):
		(val, cnt) = divmod(m1, bignum)
		(b, c) = divmod(o1, bignum)
		return (b * val + c * cnt) % MOD * bignum + cnt

	def foo(o1, o2):
		(b1, c1) = divmod(o1, bignum)
		(b2, c2) = divmod(o2, bignum)
		b = b1 * b2 % MOD
		c = (c1 * b2 + c2) % MOD
		return b * bignum + c
	(N, Q) = map(int, input().split())
	monoid_data = [A * bignum + 1 for A in map(int, input().split())]
	lst = LazySegmentTree(monoid_data, 1, bignum, fmm, fmo, foo)
	for _ in range(Q):
		(q, *k) = map(int, input().split())
		if q == 0:
			o = k[2] * bignum + k[3]
			lst.effect(k[0], k[1], o)
		else:
			print(lst.folded(k[0], k[1]) // bignum)
atc2()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline

	def op(a, b):
		(a0, a1, aa) = a
		(b0, b1, bb) = b
		return (a0 + b0, a1 + b1, aa + bb + a1 * b0)
	e = (0, 0, 0)

	def mapping(a, x, seg_len):
		if x:
			(a0, a1, aa) = a
			return (a1, a0, a0 * a1 - aa)
		else:
			return a

	def composition(x, y):
		return x ^ y
	id = 0

	class LazySegTree:

		def __init__(self, A, op=op, e=e, mapping=mapping, composition=composition, id=id, initialize=True):
			self.N = len(A)
			self.LV = (self.N - 1).bit_length()
			self.N0 = 1 << self.LV
			self.op = op
			self.e = e
			self.mapping = mapping
			self.composition = composition
			self.id = id
			if initialize:
				self.data = [self.e] * self.N0 + A + [self.e] * (self.N0 - self.N)
				for i in range(self.N0 - 1, 0, -1):
					self.data[i] = op(self.data[i * 2], self.data[i * 2 + 1])
			else:
				self.data = [self.e] * (self.N0 * 2)
			self.lazy = [id] * (self.N0 * 2)

		def _ascend(self, i):
			for _ in range(i.bit_length() - 1):
				i >>= 1
				self.data[i] = self.op(self.data[i * 2], self.data[i * 2 + 1])

		def _descend(self, idx):
			lv = idx.bit_length()
			seg_len = 1 << self.LV
			for j in range(lv - 1, 0, -1):
				seg_len >>= 1
				i = idx >> j
				x = self.lazy[i]
				if x == self.id:
					continue
				self.lazy[i * 2] = self.composition(self.lazy[i * 2], x)
				self.lazy[i * 2 + 1] = self.composition(self.lazy[i * 2 + 1], x)
				self.lazy[i] = self.id
				self.data[i * 2] = self.mapping(self.data[i * 2], x, seg_len)
				self.data[i * 2 + 1] = self.mapping(self.data[i * 2 + 1], x, seg_len)

		def apply(self, l, r, x):
			l += self.N0 - 1
			r += self.N0 - 1
			self._descend(l // (l & -l))
			self._descend(r // (r & -r) - 1)
			l_ori = l
			r_ori = r
			seg_len = 1
			while l < r:
				if l & 1:
					self.data[l] = self.mapping(self.data[l], x, seg_len)
					self.lazy[l] = self.composition(self.lazy[l], x)
					l += 1
				if r & 1:
					r -= 1
					self.data[r] = self.mapping(self.data[r], x, seg_len)
					self.lazy[r] = self.composition(self.lazy[r], x)
				l >>= 1
				r >>= 1
				seg_len <<= 1
			self._ascend(l_ori // (l_ori & -l_ori))
			self._ascend(r_ori // (r_ori & -r_ori) - 1)

		def query(self, l, r):
			l += self.N0 - 1
			r += self.N0 - 1
			self._descend(l // (l & -l))
			self._descend(r // (r & -r) - 1)
			ret_l = self.e
			ret_r = self.e
			while l < r:
				if l & 1:
					ret_l = self.op(ret_l, self.data[l])
					l += 1
				if r & 1:
					ret_r = self.op(self.data[r - 1], ret_r)
					r -= 1
				l >>= 1
				r >>= 1
			return self.op(ret_l, ret_r)
	(N, Q) = map(int, input().split())
	A_raw = list(map(int, input().split()))
	A = [None] * N
	for (i, a) in enumerate(A_raw):
		if a:
			A[i] = (0, 1, 0)
		else:
			A[i] = (1, 0, 0)
	ST = LazySegTree(A)
	for _ in range(Q):
		(t, l, r) = map(int, input().split())
		if t == 1:
			ST.apply(l, r + 1, 1)
		else:
			print(ST.query(l, r + 1)[2])
main()


from typing import Callable, List, TypeVar
S = TypeVar('S')
F = TypeVar('F')

class LazySegmentTree:
	__slots__ = ['e', 'op', 'id', 'mapping', 'composition', '_n', '_log', '_size', 'tree', 'lazy']

	def __init__(self, a: List[S], e: S, op: Callable[[S, S], S], id_: F, mapping: Callable[[F, S], S], composition: Callable[[F, F], F]) -> None:
		self.e = e
		self.op = op
		self.id = id_
		self.mapping = mapping
		self.composition = composition
		self._n = len(a)
		self._log = (self._n - 1).bit_length()
		self._size = 1 << self._log
		self.tree = [e] * self._size + a + [e] * (self._size - self._n)
		for i in range(self._size - 1, 0, -1):
			self._update(i)
		self.lazy = [id_] * self._size

	def _update(self, k: int) -> None:
		self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

	def _apply_all(self, k: int, f: F) -> None:
		self.tree[k] = self.mapping(f, self.tree[k])
		if k < self._size:
			self.lazy[k] = self.composition(f, self.lazy[k])

	def _push(self, k: int) -> None:
		self._apply_all(2 * k, self.lazy[k])
		self._apply_all(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.id

	def set(self, k: int, x: S) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = x
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def get(self, k: int) -> S:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		return self.tree[k]

	def prod(self, l: int, r: int) -> S:
		assert 0 <= l <= r <= self._n
		if l == r:
			return self.e
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r >> i)
		(sml, smr) = (self.e, self.e)
		while l < r:
			if l & 1:
				sml = self.op(sml, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.tree[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def prod_all(self) -> S:
		return self.tree[1]

	def apply(self, k: int, f: F) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = self.mapping(f, self.tree[k])
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def apply_range(self, l: int, r: int, f: F) -> None:
		assert 0 <= l <= r <= self._n
		if l == r:
			return
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r - 1 >> i)
		(l_tmp, r_tmp) = (l, r)
		while l < r:
			if l & 1:
				self._apply_all(l, f)
				l += 1
			if r & 1:
				r -= 1
				self._apply_all(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l_tmp, r_tmp)
		for i in range(1, self._log + 1):
			if l >> i << i != l:
				self._update(l >> i)
			if r >> i << i != r:
				self._update(r - 1 >> i)

	def max_right(self, l: int, g: Callable[[S], bool]) -> int:
		assert 0 <= l <= self._n
		assert g(self.e)
		if l == self._n:
			return self._n
		l += self._size
		for i in range(self._log, 0, -1):
			self._push(l >> i)
		sm = self.e
		while True:
			while not l & 1:
				l >>= 1
			if not g(self.op(sm, self.tree[l])):
				while l < self._size:
					l *= 2
					if g(self.op(sm, self.tree[l])):
						sm = self.op(sm, self.tree[l])
						l += 1
				return l - self._size
			sm = self.op(sm, self.tree[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g: Callable[[S], bool]) -> int:
		assert 0 <= r <= self._n
		assert g(self.e)
		if not r:
			return 0
		r += self._size
		for i in range(self._log, 0, -1):
			self._push(r - 1 >> i)
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not g(self.op(self.tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if g(self.op(self.tree[r], sm)):
						sm = self.op(self.tree[r], sm)
						r -= 1
				return r + 1 - self._size
			sm = self.op(self.tree[r], sm)
			if r & -r == r:
				break
		return 0
MOD = 998244353

def range_affine_range_sum():
	import sys
	readline = sys.stdin.buffer.readline
	(N, Q) = map(int, readline().split())
	A = [(i << 32) + 1 for i in map(int, readline().split())]
	e = 1
	id_ = 1 << 32

	def op(s, t):
		(sv, sn) = (s >> 32, s % (1 << 32))
		(tv, tn) = (t >> 32, t % (1 << 32))
		return ((sv + tv) % MOD << 32) + sn + tn

	def mapping(f, a):
		(fb, fc) = (f >> 32, f % (1 << 32))
		(av, an) = (a >> 32, a % (1 << 32))
		return ((fb * av + fc * an) % MOD << 32) + an

	def composition(f, g):
		(fb, fc) = (f >> 32, f % (1 << 32))
		(gb, gc) = (g >> 32, g % (1 << 32))
		return (fb * gb % MOD << 32) + (gc * fb + fc) % MOD
	tree = LazySegmentTree(A, e, op, id_, mapping, composition)
	res = []
	for _ in range(Q):
		(com, l, r, *bc) = map(int, readline().split())
		if com:
			res.append(tree.prod(l, r) >> 32)
		else:
			(b, c) = bc
			tree.apply_range(l, r, (b << 32) + c)
	print('\n'.join(map(str, res)))

def practice2_l():
	from operator import xor
	(N, _, *AX) = map(int, open(0).read().split())
	(A, TLR) = (AX[:N], AX[N:])
	dic = {0: (1, 0, 0), 1: (0, 1, 0)}
	tree = LazySegmentTree([dic[a] for a in A], e=(0, 0, 0), op=lambda m1, m2: (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0]), id_=0, mapping=lambda o, m: (m[1], m[0], m[0] * m[1] - m[2]) if o else m, composition=xor)
	res = []
	for (t, l, r) in zip(*[iter(TLR)] * 3):
		if t == 1:
			tree.apply_range(l - 1, r, 1)
		else:
			res.append(tree.prod(l - 1, r)[2])
	print('\n'.join(map(str, res)))
practice2_l()


class convolution:

	def __init__(self, a: list, b: list, mod: int):
		(self.a, self.b) = (a, b)
		(self.n, self.m) = (len(a), len(b))
		self.MOD = mod
		self.g = primitive_root_constexpr(self.MOD)

	def convolution(self) -> list:
		(n, m) = (self.n, self.m)
		(a, b) = (self.a, self.b)
		if not n or not m:
			return []
		if min(n, m) <= 60:
			if n < m:
				(n, m) = (m, n)
				(a, b) = (b, a)
			ans = [0] * (n + m - 1)
			for i in range(n):
				for j in range(m):
					ans[i + j] += a[i] * b[j] % self.MOD
					ans[i + j] %= self.MOD
			return ans
		z = 1 << ceil_pow2(n + m - 1)
		a = self.resize(a, z)
		a = self.butterfly(a)
		b = self.resize(b, z)
		b = self.butterfly(b)
		for i in range(z):
			a[i] = a[i] * b[i] % self.MOD
		a = self.butterfly_inv(a)
		a = a[:n + m - 1]
		iz = self.inv(z)
		a = [x * iz % self.MOD for x in a]
		return a

	def butterfly(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_e = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_e[i] = es[i] * now % m
				now = now * ies[i] % m
		for ph in range(1, h + 1):
			w = 1 << ph - 1
			p = 1 << h - ph
			now = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] * now % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (l - r) % m
				now = now * sum_e[bsf(~s)] % m
		return a

	def butterfly_inv(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_ie = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_ie[i] = ies[i] * now % m
				now = es[i] * now % m
		for ph in range(h, 0, -1):
			w = 1 << ph - 1
			p = 1 << h - ph
			inow = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (m + l - r) * inow % m
				inow = sum_ie[bsf(~s)] * inow % m
		return a

	@staticmethod
	def resize(array: list, sz: int) -> list:
		new_array = array + [0] * (sz - len(array))
		return new_array

	def inv(self, x: int):
		if is_prime_constexpr(self.MOD):
			assert x
			return self.mypow(x, self.MOD - 2)
		else:
			eg = inv_gcd(x)
			assert eg[0] == 1
			return eg[1]

	def mypow(self, x: int, n: int) -> int:
		assert 0 <= n
		r = 1
		m = self.MOD
		while n:
			if n & 1:
				r = r * x % m
			x = x * x % m
			n >>= 1
		return r

class dsu:

	def __init__(self, n: int):
		self._n = n
		self.parent_or_size = [-1] * self._n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a and a < self._n
		if self.parent_or_size[a] < 0:
			return a
		self.parent_or_size[a] = self.leader(self.parent_or_size[a])
		return self.parent_or_size[a]

	def size(self, a: int) -> int:
		assert 0 <= a and a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self):
		leader_buf = [0] * self._n
		group_size = [0] * self._n
		for i in range(self._n):
			leader_buf[i] = self.leader(i)
			group_size[leader_buf[i]] += 1
		result = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		result = [v for v in result if v]
		return result

class fenwick_tree:

	def __init__(self, n):
		self._n = n
		self.data = [0] * n

	def add(self, p: int, x: int):
		assert 0 <= p and p <= self._n
		p += 1
		while p <= self._n:
			self.data[p - 1] += x
			p += p & -p

	def sum(self, l: int, r: int) -> int:
		assert 0 <= l and l <= r and (r <= self._n)
		return self.__sum(r) - self.__sum(l)

	def __sum(self, r: int) -> int:
		s = 0
		while r > 0:
			s += self.data[r - 1]
			r -= r & -r
		return s

def ceil_pow2(n: int) -> int:
	x = 0
	while 1 << x < n:
		x += 1
	return x

def bsf(n: int) -> int:
	return (n & -n).bit_length() - 1

def safe_mod(x: int, m: int) -> int:
	x %= m
	if x < 0:
		x += m
	return x

class barrett:

	def __init__(self, m: int):
		self._m = m
		self.im = -1 // (m + 1)

	def umod(self):
		return self._m

	def mul(self, a: int, b: int) -> int:
		z = a
		z *= b
		x = z * im >> 64
		v = z - x * self._m
		if self._m <= v:
			v += self._m
		return v

def pow_mod_constexpr(x: int, n: int, m: int) -> int:
	if m == 1:
		return 0
	_m = m
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = r * y % _m
		y = y * y % _m
		n >>= 1
	return r

def is_prime_constexpr(n: int) -> bool:
	if n <= 1:
		return False
	if n == 2 or n == 7 or n == 61:
		return True
	if n % 2 == 0:
		return False
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for a in [2, 7, 61]:
		t = d
		y = pow_mod_constexpr(a, t, n)
		while t != n - 1 and y != 1 and (y != n - 1):
			y = y * y % n
			t <<= 1
		if y != n - 1 and t % 2 == 0:
			return False
	return True

def inv_gcd(self, a: int, b: int) -> tuple:
	a = safe_mod(a, b)
	if a == 0:
		return (b, 0)
	s = b
	t = a
	m0 = 0
	m1 = 1
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		tmp = s
		s = t
		t = tmp
		tmp = m0
		m0 = m1
		m1 = tmp
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def primitive_root_constexpr(m: int) -> int:
	if m == 2:
		return 1
	if m == 167772161:
		return 3
	if m == 469762049:
		return 3
	if m == 754974721:
		return 11
	if m == 998244353:
		return 3
	divs = [0] * 20
	divs[0] = 2
	cnt = 1
	x = (m - 1) // 2
	while x % 2 == 0:
		x //= 2
	i = 3
	while i * i <= x:
		if x % i == 0:
			divs[cnt] = i
			cnt += 1
			while x % i == 0:
				x //= i
		i += 2
	if x > 1:
		divs[cnt] = x
		cnt += 1
	g = 2
	while True:
		ok = True
		for i in range(cnt):
			if pow_mod_constexpr(g, (m - 1) // div[i], m) == 1:
				ok = False
				break
		if ok:
			return g
		g += 1

class simple_queue:

	def __init__(self):
		self.payload = []
		self.pos = 0

	def size(self):
		return len(self.payload) - self.pos

	def empty(self):
		return self.pos == len(self.payload)

	def push(self, t: int):
		self.payload.append(t)

	def front(self):
		return self.payload[self.pos]

	def clear(self):
		self.payload.clear()
		pos = 0

	def pop(self):
		self.pos += 1

	def pop_front(self):
		self.pos += 1
		return self.payload[~-self.pos]

class csr:

	def __init__(self, n: int, edges: list):
		from copy import deepcopy
		self.start = [0] * (n + 1)
		self.elist = [[] for _ in range(len(edges))]
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = deepcopy(self.start)
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(self, n: int):
		self._n = n
		self.now_ord = 0
		self.group_num = 0

	def num_vertices(self):
		return self._n

	def add_edge(self, _from: int, _to: int):
		self.edges.append((_from, [_to]))

	def scc_ids(self):
		g = csr(self._n, self.edges)
		visited = []
		low = [0] * self._n
		ord = [-1] * self._n
		ids = [0] * self._n

		def dfs(s, v: int):
			low[v] = ord[v] = self.now_ord
			self.now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				if ord[to] == -1:
					s(s, to)
					low[v] = min(low[v], low[to])
				else:
					low[v] = min(low[v], ord[to])
			if low[v] == ord[v]:
				while True:
					u = visited.pop()
					ord[u] = self._n
					ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self._n):
			if ord[i] == -1:
				dfs(dfs, i)
		for i in range(self._n):
			ids[i] = self.group_num - 1 - ids[i]
		return (self.group_num, ids)

	def scc(self):
		ids = self.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(self._n):
			groups[ids[1][i]].append(i)
		return groups

class lazy_segtree:

	def __init__(self, op, e, mapping, composition, id, v: list):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.lz = [self.id()] * self.size
		self.d = [self.e()] * (2 * self.size)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return self.e()
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r >> i)
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p: int, f):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def apply(self, l: int, r: int, f):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.__all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.__all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.__update(l >> i)
			if r >> i << i != r:
				self.__update(r >> i)

	def max_right(self, l: int, g):
		assert 0 <= l and l <= self._n
		if l == self._n:
			return self._n
		l += self.size
		for i in range(self.log, 0, -1):
			self.__push(l >> i)
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.__push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g):
		assert 0 <= r and r <= self._n
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.__push(r >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.__push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

	def __all_apply(self, k: int, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k: int):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id()

def pow_mod(x: int, n: int, m: int) -> int:
	assert 0 <= n and 1 <= m
	if m == 1:
		return 0
	bt = barrett(m)
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = bt.mul(r, y)
		y = bt.mul(y, y)
		n >>= 1
	return n

def inv_mod(x: int, m: int) -> int:
	assert 1 <= m
	z = inv_gcd(x, m)
	assert z[0] == 1
	return z[1]

def crt(r: list, m: list) -> tuple:
	assert len(r) == len(m)
	n = len(r)
	r0 = 0
	m0 = 1
	for i in range(n):
		assert 1 <= m[i]
		r1 = safe_mod(r[i], m[i])
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		bb %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

class mf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(self._n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		assert 0 <= cap
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def change_edge(self, i: int, new_cap: int, new_flow: int):
		m = len(self.pos)
		assert 0 <= i and i < m
		assert 0 <= new_flow and new_flow <= new_cap
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		_e.cap = new_cap - new_flow
		_re.cap = new_flow

	def flow(self, s: int, t: int):
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> int:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		level = [0] * self._n
		it = [0] * self._n

		def bfs():
			for i in range(self._n):
				level[i] = -1
			level[s] = 0
			que = deque([s])
			while que:
				v = que.popleft()
				for e in self.g[v]:
					if e.cap == 0 or level[e.to] >= 0:
						continue
					level[e.to] = level[v] + 1
					if e.to == t:
						return
					que.append(e.to)

		def dfs(self_, v: int, up: int) -> int:
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(it[v], len(self.g[v])):
				it[v] = i
				e = self.g[v][i]
				if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
					continue
				d = self_(self_, e.to, min(up - res, self.g[e.to][e.rev].cap))
				if d <= 0:
					continue
				self.g[v][i].cap += d
				self.g[e.to][e.rev].cap -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self._n):
				it[i] = 0
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s: int) -> list:
		visited = [False] * self._n
		que = deque([s])
		while que:
			p = que.popleft()
			visited[p] = True
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que.append(e.to)
		return visited

	class _edge:

		def __init__(s, to: int, rev: int, cap: int):
			s.to = to
			s.rev = rev
			s.cap = cap

class mcf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int, cost: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap, cost))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0, -cost))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int, cost: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow
			s.cost = cost

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def flow(self, s: int, t: int) -> edge:
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> edge:
		return self.__slope(s, t, flow_limit)[-1]

	def slope(self, s: int, t: int) -> list:
		return self.slope_(s, t, self.numeric_limits_max)

	def slope_(self, s: int, t: int, flow_limit: int) -> list:
		return self.__slope(s, t, flow_limit)

	def __slope(self, s: int, t: int, flow_limit: int) -> list:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		assert s != t
		dual = [0] * self._n
		dist = [0] * self._n
		(pv, pe) = ([-1] * self._n, [-1] * self._n)
		vis = [False] * self._n

		def dual_ref():
			for i in range(self._n):
				dist[i] = self.numeric_limits_max
				pv[i] = -1
				pe[i] = -1
				vis[i] = False

			class Q:

				def __init__(s, key: int, to: int):
					s.key = key
					s.to = to

				def __lt__(s, r):
					return s.key < r.key
			que = []
			dist[s] = 0
			heappush(que, Q(0, s))
			while que:
				v = heappop(que).to
				if vis[v]:
					continue
				vis[v] = True
				if v == t:
					break
				for i in range(len(self.g[v])):
					e = self.g[v][i]
					if vis[e.to] or not e.cap:
						continue
					cost = e.cost - dual[e.to] + dual[v]
					if dist[e.to] - dist[v] > cost:
						dist[e.to] = dist[v] + cost
						pv[e.to] = v
						pe[e.to] = i
						heappush(que, Q(dist[e.to], e.to))
			if not vis[t]:
				return False
			for v in range(self._n):
				if not vis[v]:
					continue
				dual[v] -= dist[t] - dist[v]
			return True
		flow = 0
		cost = 0
		prev_cost = -1
		result = []
		result.append((flow, cost))
		while flow < flow_limit:
			if not dual_ref():
				break
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.g[pv[v]][pe[v]].cap)
				v = pv[v]
			v = t
			while v != s:
				e = self.g[pv[v]][pe[v]]
				e.cap -= c
				self.g[v][e.rev].cap += c
				v = pv[v]
			d = -dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result.pop()
			result.append((flow, cost))
			prev_cost = cost
		return result

	class _edge:

		def __init__(s, to: int, rev: int, cap: int, cost: int):
			s.to = to
			s.rev = rev
			s.cap = cap
			s.cost = cost

class Mint:
	modint1000000007 = 1000000007
	modint998244353 = 998244353

	def __init__(self, v: int=0):
		self.m = self.modint1000000007
		self.x = v % self.__umod()

	def inv(self):
		if is_prime_constexpr(self.__umod()):
			assert self.x
			return self.pow_(self.__umod() - 2)
		else:
			eg = inv_gcd(self.x, self.m)
			assert eg[0] == 1
			return eg[2]

	def __str__(self):
		return str(self.x)

	def __le__(self, other):
		return self.x <= Mint.__get_val(other)

	def __lt__(self, other):
		return self.x < Mint.__get_val(other)

	def __ge__(self, other):
		return self.x >= Mint.__get_val(other)

	def __gt(self, other):
		return self.x > Mint.__get_val(other)

	def __eq__(self, other):
		return self.x == Mint.__get_val(other)

	def __iadd__(self, other):
		self.x += Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x -= self.__umod()
		return self

	def __add__(self, other):
		_v = Mint(self.x)
		_v += other
		return _v

	def __isub__(self, other):
		self.x -= Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x += self.__umod()
		return self

	def __sub__(self, other):
		_v = Mint(self.x)
		_v -= other
		return _v

	def __rsub__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v -= self
		return _v

	def __imul__(self, other):
		self.x = self.x * Mint.__get_val(other) % self.__umod()
		return self

	def __mul__(self, other):
		_v = Mint(self.x)
		_v *= other
		return _v

	def __itruediv__(self, other):
		self.x = self.x / Mint.__get_val(other) % self.__umod()
		return self

	def __truediv__(self, other):
		_v = Mint(self.x)
		_v /= other
		return _v

	def __rtruediv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v /= self
		return _v

	def __ifloordiv__(self, other):
		other = other if isinstance(other, Mint) else Mint(other)
		self *= other.inv()
		return self

	def __floordiv__(self, other):
		_v = Mint(self.x)
		_v //= other
		return _v

	def __rfloordiv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v //= self
		return _v

	def __pow__(self, other):
		_v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
		return _v

	def __rpow__(self, other):
		_v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
		return _v

	def __imod__(self, other):
		self.x %= Mint.__get_val(other)
		return self

	def __mod__(self, other):
		_v = Mint(self.x)
		_v %= other
		return _v

	def __rmod__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v %= self
		return _v

	def __ilshift__(self, other):
		self.x <<= Mint.__get_val(other)
		return self

	def __irshift__(self, other):
		self.x >>= Mint.__get_val(other)
		return self

	def __lshift__(self, other):
		_v = Mint(self.x)
		_v <<= other
		return _v

	def __rshift__(self, other):
		_v = Mint(self.x)
		_v >>= other
		return _v

	def __rlshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v <<= self
		return _v

	def __rrshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v >>= self
		return _v
	__repr__ = __str__
	__radd__ = __add__
	__rmul__ = __mul__

	def __umod(self):
		return self.m

	@staticmethod
	def __get_val(val):
		return val.x if isinstance(val, Mint) else val

	def pow_(self, n: int):
		assert 0 <= n
		x = Mint(self.x)
		r = 1
		while n:
			if n & 1:
				r *= x
			x *= x
			n >>= 1
		return r

	def val(self):
		return self.x

	def mod(self):
		return self.m

	def raw(self, v):
		x = Mint()
		x.x = v
		return x

class scc_graph_sub:

	def __init__(self, n):
		self.internal = scc_graph(n)

	def add_edge(self, _from, _to):
		n = self.internal.num_vertices()
		assert 0 <= _from and _from < n
		assert 0 <= _to and _to < n
		self.internal.add_edge(_from, _to)

	def scc(self):
		return self.internal.scc()

class segtree:

	def __init__(self, op, e, v: list):
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.op = op
		self.e = e
		self.d = [self.e()] * (self.size * 2)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> i)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		return self.d[p + self.size]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		l += self.size
		r += self.size
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def max_right(self, l: int, f):
		assert 0 <= l and l <= self._n
		assert f(self.e())
		if l == self._n:
			return self._n
		l += self.size
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not f(self.op(sm, self.d[l])):
				while l < self.size:
					l = 2 * l
					if f(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, f):
		assert 0 <= r and r <= self._n
		assert f(self.e())
		if r == 0:
			return 0
		r += self.size
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not f(self.op(self.d[r], sm)):
				while r < self.size:
					r = 2 * r + 1
					if f(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

def sa_native(s: list):
	from functools import cmp_to_key

	def mycmp(r, l):
		if l == r:
			return -1
		while l < n and r < n:
			if s[l] != s[r]:
				return 1 if s[l] < s[r] else -1
			l += 1
			r += 1
		return 1 if l == n else -1
	n = len(s)
	sa = [i for i in range(n)]
	sa.sort(key=cmp_to_key(mycmp))
	return sa

def sa_doubling(s: list):
	from functools import cmp_to_key

	def mycmp(y, x):
		if rnk[x] != rnk[y]:
			return 1 if rnk[x] < rnk[y] else -1
		rx = rnk[x + k] if x + k < n else -1
		ry = rnk[y + k] if y + k < n else -1
		return 1 if rx < ry else -1
	n = len(s)
	sa = [i for i in range(n)]
	rnk = s
	tmp = [0] * n
	k = 1
	while k < n:
		sa.sort(key=cmp_to_key(mycmp))
		tmp[sa[0]] = 0
		for i in range(1, n):
			tmp[sa[i]] = tmp[sa[i - 1]]
			if mycmp(sa[i], sa[i - 1]) == 1:
				tmp[sa[i]] += 1
		(tmp, rnk) = (rnk, tmp)
		k *= 2
	return sa

def sa_is(s: list, upper: int):
	THRESHOLD_NATIVE = 10
	THRESHOLD_DOUBLING = 40
	n = len(s)
	if n == 0:
		return []
	if n == 1:
		return [0]
	if n == 2:
		if s[0] < s[1]:
			return [0, 1]
		else:
			return [1, 0]
	if n < THRESHOLD_NATIVE:
		return sa_native(s)
	if n < THRESHOLD_DOUBLING:
		return sa_doubling(s)
	sa = [0] * n
	ls = [False] * n
	for i in range(n - 2, -1, -1):
		ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
	sum_l = [0] * (upper + 1)
	sum_s = [0] * (upper + 1)
	for i in range(n):
		if not ls[i]:
			sum_s[s[i]] += 1
		else:
			sum_l[s[i] + 1] += 1
	for i in range(upper + 1):
		sum_s[i] += sum_l[i]
		if i < upper:
			sum_l[i + 1] += sum_s[i]

	def induce(lms: list):
		from copy import copy
		for i in range(n):
			sa[i] = -1
		buf = [0] * (upper + 1)
		buf = copy(sum_s)
		for d in lms:
			if d == n:
				continue
			sa[buf[s[d]]] = d
			buf[s[d]] += 1
		buf = copy(sum_l)
		sa[buf[s[n - 1]]] = n - 1
		buf[s[n - 1]] += 1
		for i in range(n):
			v = sa[i]
			if v >= 1 and (not ls[v - 1]):
				sa[buf[s[v - 1]]] = v - 1
				buf[s[v - 1]] += 1
		buf = copy(sum_l)
		for i in range(n - 1, -1, -1):
			v = sa[i]
			if v >= 1 and ls[v - 1]:
				buf[s[v - 1] + 1] -= 1
				sa[buf[s[v - 1] + 1]] = v - 1
	lms_map = [-1] * (n + 1)
	m = 0
	for i in range(1, n):
		if not ls[i - 1] and ls[i]:
			lms_map[i] = m
			m += 1
	lms = [i for i in range(1, n) if not ls[i - 1] and ls[i]]
	induce(lms)
	if m:
		sorted_lms = [v for v in sa if lms_map[v] != -1]
		rec_s = [0] * m
		rec_upper = 0
		rec_s[lms_map[sorted_lms[0]]] = 0
		for i in range(1, m):
			l = sorted_lms[i - 1]
			r = sorted_lms[i]
			end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
			end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
			same = True
			if end_l - l != end_r - r:
				same = False
			else:
				while l < end_l:
					if s[l] != s[r]:
						break
					l += 1
					r += 1
				if l == n or s[l] != s[r]:
					same = False
			if not same:
				rec_upper += 1
			rec_s[lms_map[sorted_lms[i]]] = rec_upper
		rec_sa = sa_is(rec_s, rec_upper)
		for i in range(m):
			sorted_lms[i] = lms[rec_sa[i]]
		induce(sorted_lms)
	return sa

def suffix_array(s: list, upper: int):
	assert 0 <= upper
	for d in s:
		assert 0 <= d and d <= upper
	sa = sa_is(s, upper)
	return sa

def suffix_array2(s: list):
	from functools import cmp_to_key
	n = len(s)
	idx = [i for i in range(n)]
	idx.sort(key=cmp_to_key(lambda l, r: s[l] < s[r]))
	s2 = [0] * n
	now = 0
	for i in range(n):
		if i and s[idx[i - 1]] != s[idx[i]]:
			now += 1
		s2[idx[i]] = now
	return sa_is(s2, now)

def suffix_array3(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return sa_is(s2, 255)

def lcp_array(s: list, sa: list):
	n = len(s)
	assert n >= 1
	rnk = [0] * n
	for i in range(n):
		rnk[sa[i]] = i
	lcp = [0] * (n - 1)
	h = 0
	for i in range(n):
		if h > 0:
			h -= 1
		if rnk[i] == 0:
			continue
		j = sa[rnk[i] - 1]
		while j + h < n and i + h < n:
			if s[j + h] != s[i + h]:
				break
			h += 1
		lcp[rnk[i] - 1] = h
	return lcp

def lcp_array2(s: str, sa: list):
	n = len(s)
	s2 = list(map(ord, s))
	return lcp_array(s2, sa)

def z_algorithm(s: list):
	n = len(s)
	if n == 0:
		return []
	z = [-1] * n
	z[0] = 0
	j = 0
	for i in range(1, n):
		k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
		while i + k < n and s[k] == s[i + k]:
			k += 1
		z[i] = k
		if j + z[j] < i + z[i]:
			j = i
	z[0] = n
	return z

def z_algorithm2(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return z_algorithm(s2)

class two_sat:

	def __init__(self, n: int):
		self._n = n
		self.scc = scc_graph(2 * n)
		self._answer = [False] * n

	def add_clause(self, i: int, f: bool, j: int, g: bool):
		assert 0 <= i and i < self._n
		assert 0 <= j and j < self._n
		self.scc.add_edge(2 * i + (not f), 2 * j + g)
		self.scc.add_edge(2 * j + (not g), 2 * i + f)

	def satisfiable(self) -> bool:
		_id = self.scc.scc_ids()[1]
		for i in range(self._n):
			if _id[2 * i] == _id[2 * i + 1]:
				return False
			self._answer[i] = _id[2 * i] < _id[2 * i + 1]
		return True

	def answer(self):
		return self._answer
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

def Main_A():
	(n, q) = read_ints()
	d = dsu(n)
	for _ in range(q):
		(t, u, v) = read_ints()
		if t == 0:
			d.merge(u, v)
		else:
			print(int(d.same(u, v)))

def Main_B():
	(n, q) = read_ints()
	a = read_int_list()
	fw = fenwick_tree(n)
	for (i, x) in enumerate(a):
		fw.add(i, x)
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			fw.add(query[1], query[2])
		else:
			print(fw.sum(query[1], query[2]))

def Main_C():
	for _ in range(read_int()):
		(n, m, a, b) = read_ints()
		print(floor_sum(n, m, a, b))

def Main_D():
	(n, m) = read_ints()
	grid = [list(read_str()) for _ in range(n)]
	mf = mf_graph(n * m + 2)
	start = n * m
	end = start + 1
	dir = [(1, 0), (0, 1)]
	for y in range(n):
		for x in range(m):
			if (y + x) % 2 == 0:
				mf.add_edge(start, m * y + x, 1)
			else:
				mf.add_edge(m * y + x, end, 1)
			if grid[y][x] == '.':
				for (dy, dx) in dir:
					ny = y + dy
					nx = x + dx
					if ny < n and nx < m and (grid[ny][nx] == '.'):
						(f, t) = (y * m + x, ny * m + nx)
						if (y + x) % 2:
							(f, t) = (t, f)
						mf.add_edge(f, t, 1)
	ans = mf.flow(start, end)
	for y in range(n):
		for x in range(m):
			for e in mf.g[y * m + x]:
				(to, rev, cap) = (e.to, e.rev, e.cap)
				(ny, nx) = divmod(to, m)
				if (y + x) % 2 == 0 and cap == 0 and (to != start) and (to != end) and (y * m + x != start) and (y * m + x != end):
					if y + 1 == ny:
						grid[y][x] = 'v'
						grid[ny][nx] = '^'
					elif y == ny + 1:
						grid[y][x] = '^'
						grid[ny][nx] = 'v'
					elif x + 1 == nx:
						grid[y][x] = '>'
						grid[ny][nx] = '<'
					elif x == nx + 1:
						grid[y][x] = '<'
						grid[ny][nx] = '>'
	print(ans)
	print(*[''.join(ret) for ret in grid], sep='\n')

def Main_E():
	(n, k) = read_ints()
	a = [read_int_list() for _ in range(n)]
	mcf = mcf_graph(n * 2 + 2)
	s = n * 2
	t = n * 2 + 1
	for i in range(n):
		mcf.add_edge(s, i, k, 0)
		mcf.add_edge(i + n, t, k, 0)
	mcf.add_edge(s, t, n * k, INF)
	for i in range(n):
		for j in range(n):
			mcf.add_edge(i, n + j, 1, INF - a[i][j])
	result = mcf.flow_(s, t, n * k)
	print(n * k * INF - result[1])
	grid = [['.'] * n for _ in range(n)]
	edges = mcf.edges()
	for e in edges:
		if e._from == s or e._to == t or e.flow == 0:
			continue
		grid[e._from][e._to - n] = 'X'
	print(*[''.join(g) for g in grid], sep='\n')

def Main_F():
	MOD = 998244353
	(n, m) = read_ints()
	a = read_int_list()
	b = read_int_list()
	a = [x % MOD for x in a]
	b = [x % MOD for x in b]
	cnv = convolution(a, b, MOD)
	ans = cnv.convolution()
	print(*ans)

def Main_G():
	sys.setrecursionlimit(10 ** 6)
	(n, m) = read_ints()
	scc = scc_graph(n)
	for _ in range(m):
		(a, b) = read_ints()
		scc.add_edge(a, b)
	ans = scc.scc()
	print(len(ans))
	for v in ans:
		print(len(v), ' '.join(map(str, v[::-1])))

def Main_H():
	(n, d) = read_ints()
	xy = [read_int_list() for _ in range(n)]
	tw = two_sat(n)
	for i in range(n):
		for j in range(i + 1, n):
			for x in range(2):
				if abs(xy[i][0] - xy[j][0]) < d:
					tw.add_clause(i, False, j, False)
				if abs(xy[i][0] - xy[j][1]) < d:
					tw.add_clause(i, False, j, True)
				if abs(xy[i][1] - xy[j][0]) < d:
					tw.add_clause(i, True, j, False)
				if abs(xy[i][1] - xy[j][1]) < d:
					tw.add_clause(i, True, j, True)
	if not tw.satisfiable():
		print('No')
		exit()
	print('Yes')
	ans = tw.answer()
	for (i, flag) in enumerate(ans):
		print(xy[i][0] if flag else xy[i][1])

def Main_I():
	s = read_str()
	sa = suffix_array3(s)
	ans = len(s) * (len(s) + 1) // 2
	for x in lcp_array2(s, sa):
		ans -= x
	print(ans)

def Main_J():

	def op(l, r):
		return max(l, r)

	def e():
		return -1

	def f(n):
		return n < r
	(n, q) = read_ints()
	a = read_int_list()
	seg = segtree(op, e, a)
	query = [read_ints() for _ in range(q)]
	for i in range(q):
		(t, l, r) = query[i]
		if t == 1:
			seg.set_(~-l, r)
		elif t == 2:
			print(seg.prod(~-l, r))
		else:
			print(seg.max_right(~-l, f) + 1)

def Main_K():
	p = 998244353

	def op(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 + r1) % p << 32) + l2 + r2

	def e():
		return 0

	def mapping(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 * r1 + l2 * r2) % p << 32) + r2

	def composition(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return (l1 * r1 % p << 32) + (l1 * r2 + l2) % p

	def id():
		return 1 << 32
	(n, q) = read_ints()
	A = read_int_list()
	A = [(x << 32) + 1 for x in A]
	seg = lazy_segtree(op, e, mapping, composition, id, A)
	ans = []
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			(l, r, b, c) = query[1:]
			seg.apply(l, r, (b << 32) + c)
		else:
			(l, r) = query[1:]
			print(seg.prod(l, r) >> 32)

def Main_L():

	def op(l: tuple, r: tuple):
		return (l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0])

	def e():
		return (0, 0, 0)

	def mapping(l: bool, r: tuple):
		if not l:
			return r
		return (r[1], r[0], r[1] * r[0] - r[2])

	def composition(l: bool, r: bool):
		return l ^ r

	def id():
		return False
	(n, q) = read_ints()
	A = read_int_list()
	query = [read_ints() for _ in range(q)]
	a = [(1, 0, 0) if i == 0 else (0, 1, 0) for i in A]
	seg = lazy_segtree(op, e, mapping, composition, id, a)
	for (t, l, r) in query:
		if t == 1:
			seg.apply(~-l, r, True)
		else:
			print(seg.prod(~-l, r)[2])
Main_L()


from typing import Callable, List, TypeVar
S = TypeVar('S')
F = TypeVar('F')

class LazySegmentTree:
	__slots__ = ['e', 'op', 'id', 'mapping', 'composition', '_n', '_log', '_size', 'tree', 'lazy']

	def __init__(self, a: List[S], e: S, op: Callable[[S, S], S], id_: F, mapping: Callable[[F, S], S], composition: Callable[[F, F], F]) -> None:
		self.e = e
		self.op = op
		self.id = id_
		self.mapping = mapping
		self.composition = composition
		self._n = len(a)
		self._log = (self._n - 1).bit_length()
		self._size = 1 << self._log
		self.tree = [e] * self._size + a + [e] * (self._size - self._n)
		for i in range(self._size - 1, 0, -1):
			self._update(i)
		self.lazy = [id_] * self._size

	def _update(self, k: int) -> None:
		self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

	def _apply_all(self, k: int, f: F) -> None:
		self.tree[k] = self.mapping(f, self.tree[k])
		if k < self._size:
			self.lazy[k] = self.composition(f, self.lazy[k])

	def _push(self, k: int) -> None:
		self._apply_all(2 * k, self.lazy[k])
		self._apply_all(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.id

	def set(self, k: int, x: S) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = x
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def get(self, k: int) -> S:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		return self.tree[k]

	def prod(self, l: int, r: int) -> S:
		assert 0 <= l <= r <= self._n
		if l == r:
			return self.e
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r >> i)
		(sml, smr) = (self.e, self.e)
		while l < r:
			if l & 1:
				sml = self.op(sml, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.tree[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def prod_all(self) -> S:
		return self.tree[1]

	def apply(self, k: int, f: F) -> None:
		assert 0 <= k < self._n
		k += self._size
		for i in range(self._log, 0, -1):
			self._push(k >> i)
		self.tree[k] = self.mapping(f, self.tree[k])
		for i in range(1, self._log + 1):
			self._update(k >> i)

	def apply_range(self, l: int, r: int, f: F) -> None:
		assert 0 <= l <= r <= self._n
		if l == r:
			return
		l += self._size
		r += self._size
		for i in range(self._log, 0, -1):
			if l >> i << i != l:
				self._push(l >> i)
			if r >> i << i != r:
				self._push(r - 1 >> i)
		(l_tmp, r_tmp) = (l, r)
		while l < r:
			if l & 1:
				self._apply_all(l, f)
				l += 1
			if r & 1:
				r -= 1
				self._apply_all(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l_tmp, r_tmp)
		for i in range(1, self._log + 1):
			if l >> i << i != l:
				self._update(l >> i)
			if r >> i << i != r:
				self._update(r - 1 >> i)

	def max_right(self, l: int, g: Callable[[S], bool]) -> int:
		assert 0 <= l <= self._n
		assert g(self.e)
		if l == self._n:
			return self._n
		l += self._size
		for i in range(self._log, 0, -1):
			self._push(l >> i)
		sm = self.e
		while True:
			while not l & 1:
				l >>= 1
			if not g(self.op(sm, self.tree[l])):
				while l < self._size:
					l *= 2
					if g(self.op(sm, self.tree[l])):
						sm = self.op(sm, self.tree[l])
						l += 1
				return l - self._size
			sm = self.op(sm, self.tree[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g: Callable[[S], bool]) -> int:
		assert 0 <= r <= self._n
		assert g(self.e)
		if not r:
			return 0
		r += self._size
		for i in range(self._log, 0, -1):
			self._push(r - 1 >> i)
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not g(self.op(self.tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if g(self.op(self.tree[r], sm)):
						sm = self.op(self.tree[r], sm)
						r -= 1
				return r + 1 - self._size
			sm = self.op(self.tree[r], sm)
			if r & -r == r:
				break
		return 0

def main():
	import sys
	readline = sys.stdin.buffer.readline
	(N, Q) = map(int, readline().split())
	monoid_data = [(0, 1, 0) if A == b'1' else (1, 0, 0) for A in readline().split()]

	def fmm(m1, m2):
		return (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0])

	def fmo(o1, m1):
		if o1:
			return (m1[1], m1[0], m1[0] * m1[1] - m1[2])
		else:
			return m1

	def foo(o1, o2):
		return o1 ^ o2
	lst = LazySegmentTree(a=monoid_data, e=(0, 0, 0), op=fmm, id_=0, mapping=fmo, composition=foo)
	ans = []
	for _ in range(Q):
		(T, L, R) = map(int, readline().split())
		if T == 1:
			lst.apply_range(L - 1, R, 1)
		else:
			ans.append(lst.prod(L - 1, R)[2])
	print('\n'.join(map(str, ans)))
main()


class SegmentTreeLazy:

	def __init__(self, arr, ti, ei, func, op, merge):
		self.h = (len(arr) - 1).bit_length()
		self.n = 2 ** self.h
		self.func = func
		self.op = op
		self.merge = merge
		self.ti = ti
		self.ei = ei
		self.val = [ti for _ in range(2 * self.n)]
		for i in range(len(arr)):
			self.val[self.n + i] = arr[i]
		for i in range(1, self.n)[::-1]:
			self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
		self.laz = [ei for _ in range(2 * self.n)]

	def reflect(self, k):
		if self.laz[k] == self.ei:
			return self.val[k]
		return self.op(self.val[k], self.laz[k])

	def propagate(self, k):
		if self.laz[k] == self.ei:
			return
		self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
		self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
		self.val[k] = self.reflect(k)
		self.laz[k] = self.ei

	def thrust(self, k):
		for i in range(1, self.h + 1)[::-1]:
			self.propagate(k >> i)

	def recalc(self, k):
		while k:
			k >>= 1
			self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

	def update(self, lt, rt, x):
		lt += self.n
		rt += self.n
		vl = lt
		vr = rt
		self.thrust(lt)
		self.thrust(rt - 1)
		while rt - lt > 0:
			if lt & 1:
				self.laz[lt] = self.merge(self.laz[lt], x)
				lt += 1
			if rt & 1:
				rt -= 1
				self.laz[rt] = self.merge(self.laz[rt], x)
			lt >>= 1
			rt >>= 1
		self.recalc(vl)
		self.recalc(vr - 1)

	def query(self, lt, rt):
		lt += self.n
		rt += self.n
		self.thrust(lt)
		self.thrust(rt - 1)
		vl = vr = self.ti
		while rt - lt > 0:
			if lt & 1:
				vl = self.func(vl, self.reflect(lt))
				lt += 1
			if rt & 1:
				rt -= 1
				vr = self.func(self.reflect(rt), vr)
			lt >>= 1
			rt >>= 1
		return self.func(vl, vr)
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))

def func(x, y):
	(x0, x1, x2) = x
	(y0, y1, y2) = y
	return (x0 + y0, x1 + y1, x2 + y2 + x1 * y0)

def op(x, p):
	(x0, x1, x2) = x
	if p:
		return (x1, x0, x0 * x1 - x2)
	else:
		return (x0, x1, x2)

def merge(p, q):
	return p ^ q
arr = [(1 - a, a, 0) for a in A]
ti = (0, 0, 0)
ei = 0
st = SegmentTreeLazy(arr, ti, ei, func, op, merge)
res = list()
for _ in range(Q):
	(t, l, r) = map(int, input().split())
	if t == 1:
		st.update(l - 1, r, 1)
	else:
		res.append(st.query(l - 1, r)[2])
print('\n'.join(map(str, res)))