AtCoder Library Practice Contest - Segment Tree

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

The type of i-th query is represented by T_i.

* T_i=1: You are given two integers X_i,V_i. Replace the value of A_{X_i} with V_i.
* T_i=2: You are given two integers L_i,R_i. Calculate the maximum value among A_{L_i},A_{L_i+1},\cdots,A_{R_i}.
* T_i=3: You are given two integers X_i,V_i. Calculate the minimum j such that X_i \leq j \leq N, V_i \leq A_j. If there is no such j, answer j=N+1 instead.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 0 \leq A_i \leq 10^9
* 1 \leq Q \leq 2 \times 10^5
* 1 \leq T_i \leq 3
* 1 \leq X_i \leq N, 0 \leq V_i \leq 10^9 (T_i=1,3)
* 1 \leq L_i \leq R_i \leq N (T_i=2)
* 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
First query
Second query
\vdots
Q-th query


Each query is given in the following format:

If T_i=1,3,


T_i X_i V_i


If T_i=2,


T_i L_i R_i


Output

For each query with T_i=2, 3, print the answer.

Example

Input

5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 3


Output

3
3
2
6

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
class segtree:
	sta = -1
	func = max

	def __init__(self, n):
		self.n = n
		self.size = 1 << n.bit_length()
		self.tree = [self.sta] * (2 * self.size)

	def build(self, list):
		for (i, x) in enumerate(list, self.size):
			self.tree[i] = x
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

	def set(self, i, x):
		i += self.size
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

	def get(self, l, r):
		l += self.size
		r += self.size
		res = self.sta
		while l < r:
			if l & 1:
				res = self.func(self.tree[l], res)
				l += 1
			if r & 1:
				res = self.func(self.tree[r - 1], res)
			l >>= 1
			r >>= 1
		return res

	def max_right(self, l, x):
		if l == self.n:
			return l
		l += self.size
		res = self.sta
		check = True
		while check or l & -l != l:
			check = False
			while l % 2 == 0:
				l >>= 1
			if not self.func(res, self.tree[l]) < x:
				while l < self.size:
					l <<= 1
					if self.func(res, self.tree[l]) < x:
						res = self.func(res, self.tree[l])
						l += 1
				return l - self.size
			res = self.func(res, self.tree[l])
			l += 1
		return self.n
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
seg = segtree(n)
seg.build(a)
for _ in range(q):
	(t, x, v) = map(int, input().split())
	if t == 1:
		seg.set(x - 1, v)
	elif t == 2:
		print(seg.get(x - 1, v))
	else:
		print(seg.max_right(x - 1, v) + 1)


from typing import Callable, List, Union
T = Union[int, str]

class SegmentTree:
	__slots__ = ['_n', '_log', '_size', 'op', 'e', 'tree']

	def __init__(self, initial_values: List[T], op: Callable[[T, T], T], e: T) -> None:
		self._n = len(initial_values)
		self._log = (self._n - 1).bit_length()
		self._size = 1 << self._log
		self.op = op
		self.e = e
		self.tree = [e] * 2 * self._size
		for (i, a) in enumerate(initial_values, self._size):
			self[i] = a
		for i in range(self._size - 1, 0, -1):
			self._update(i)

	def __getitem__(self, k: int) -> T:
		return self.tree[k]

	def __setitem__(self, k: int, value: T) -> None:
		self.tree[k] = value

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

	def get(self, index: int) -> T:
		assert 0 <= index < self._n
		return self[index + self._size]

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

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

	def prod_all(self) -> T:
		return self[1]

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

	def min_left(self, r: int, f: Callable[[T], bool]) -> int:
		assert 0 <= r <= self._n
		assert f(self.e)
		if not r:
			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[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if f(self.op(self[r], sm)):
						sm = self.op(self[r], sm)
						r -= 1
				return r + 1 - self._size
			if r & -r == r:
				break
		return 0

def practice2_j():
	(N, _, *AQ) = map(int, open(0).read().split())
	(A, Q) = (AQ[:N], AQ[N:])
	tree = SegmentTree(A, max, -1)
	res = []
	for (t, x, y) in zip(*[iter(Q)] * 3):
		if t == 1:
			tree.set(x - 1, y)
		elif t == 2:
			res.append(tree.prod(x - 1, y))
		else:
			res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
	print('\n'.join(map(str, res)))
practice2_j()


class SegmentTree:

	def __init__(self, n, func=lambda x, y: max(x, y), default_val=-float('inf'), init_list=None):
		assert n > 0 and (not init_list or len(init_list) <= n)
		self.n = n
		self.leaf_n = 1
		while n > self.leaf_n:
			self.leaf_n <<= 1
		self.node_n = (self.leaf_n << 1) - 1
		self.offset = self.leaf_n - 1
		self.tree = [default_val] * self.node_n
		self.default_val = default_val
		self.f = func
		if init_list:
			self.tree[self.offset:self.offset + n] = init_list
			self.update_all()

	def set_values(self, val_list):
		n = len(val_list)
		assert self.leaf_n >= n
		self.tree[self.offset:self.offset + n] = val_list

	def set_value(self, index, val):
		assert 0 <= index < self.leaf_n
		self.tree[self.offset + index] = val

	def get_value(self, index):
		assert 0 <= index < self.leaf_n
		return self.tree[self.offset + index]

	def update_all(self):
		l = self.offset
		n = self.leaf_n
		while l > 0:
			for i in range(l, l + n, 2):
				self.tree[i >> 1] = self.f(self.tree[i], self.tree[i + 1])
			l >>= 1
			n >>= 1

	def update(self, index, val):
		assert 0 <= index < self.leaf_n
		i = self.offset + index
		self.tree[i] = val
		while i > 0:
			if i & 1 == 0:
				i -= 1
			self.tree[i >> 1] = self.f(self.tree[i], self.tree[i + 1])
			i >>= 1

	def query(self, l, r):
		assert 0 <= l <= r < self.leaf_n
		left_val = self.default_val
		right_val = self.default_val
		l += self.offset
		r += self.offset
		while l < r:
			if l & 1 == 0:
				left_val = self.f(left_val, self.tree[l])
			if r & 1 == 1:
				right_val = self.f(self.tree[r], right_val)
				r -= 1
			l >>= 1
			r = (r >> 1) - 1
		if l == r:
			left_val = self.f(left_val, self.tree[l])
		return self.f(left_val, right_val)

	def search_max_right(self, l, check_func):
		assert 0 <= l < self.leaf_n and check_func(self.default_val)
		i = l + self.offset
		if not check_func(self.tree[i]):
			return -1
		left_val = self.default_val
		while True:
			while i & 1 != 0:
				i >>= 1
			x = self.f(left_val, self.tree[i])
			if not check_func(x):
				while i < self.offset:
					i = (i << 1) + 1
					x = self.f(left_val, self.tree[i])
					if check_func(x):
						left_val = x
						i += 1
				return i - self.offset - 1
			left_val = x
			i += 1
			if i & i + 1 == 0:
				return self.n - 1

	def search_min_left(self, r, check_func):
		assert 0 <= r < self.leaf_n and check_func(self.default_val)
		i = r + self.offset
		if not check_func(self.tree[i]):
			return -1
		right_val = self.default_val
		while True:
			while i & 1 == 0 and i > 0:
				i = i - 1 >> 1
			x = self.f(self.tree[i], right_val)
			if not check_func(x):
				while i < self.offset:
					i = i + 1 << 1
					x = self.f(self.tree[i], right_val)
					if check_func(x):
						right_val = x
						i -= 1
				return i - self.offset + 1
			right_val = x
			if i & i + 1 == 0:
				return 0
			i -= 1
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.reverse()
st = SegmentTree(n, max, 0, a)
ans = []
for _ in range(q):
	(t, x, v) = map(int, input().split())
	if t == 1:
		st.update(n - x, v)
	elif t == 2:
		ans.append(st.query(n - v, n - x))
	elif v == 0:
		ans.append(x)
	else:
		i = st.search_min_left(n - x, lambda y: y < v)
		if i < 0:
			ans.append(x)
		else:
			ans.append(n - i + 1)
for x in ans:
	print(x)


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_J()


import itertools

def hyperlist(*dim, **kwarg):
	default_factory = kwarg.pop('default_factory', None)
	ranges = [range(n) for n in dim]
	h = [None] * dim[0]
	for dd in range(1, len(dim)):
		for u in itertools.product(*ranges[:dd]):
			hyperlist_setitem(h, u, [None] * dim[dd])
	if default_factory:
		for u in itertools.product(*ranges):
			hyperlist_setitem(h, u, default_factory())
	return h

def hyperlist_setitem(h, u, a):
	ptr = h
	for i in u[:-1]:
		ptr = ptr[i]
	ptr[u[-1]] = a

def hyperlist_getitem(h, u):
	ptr = h
	for i in u:
		ptr = ptr[i]
	return ptr
import operator
import collections
import itertools
import functools
import math as m
try:
	m.prod
except AttributeError:

	def _prod(iterable, start=1):
		for x in iterable:
			start *= x
		return start
	m.prod = _prod

class RangeOperators(object):
	__slots__ = ['new', 'query', 'q_inverse', 'update', 'u_distributive', 'u_commutative']
	_defaults = dict(new=int, query=operator.add, q_inverse=operator.sub, update=operator.add, u_distributive=lambda t, x, w: t + x * w, u_commutative=True)

	def __init__(self, **kwarg):
		d = kwarg or self._defaults
		for (k, v) in d.items():
			setattr(self, k, v)
MAXQUERY = RangeOperators(new=int, query=max, q_inverse=None, update=operator.add, u_distributive=lambda t, x, w: t + x, u_commutative=True)
MINQUERY = RangeOperators(new=int, query=min, q_inverse=None, update=operator.add, u_distributive=lambda t, x, w: t + x, u_commutative=True)
SETUPDATE = RangeOperators(new=int, query=operator.add, q_inverse=operator.sub, update=lambda t, x: x, u_distributive=lambda t, x, w: x * w, u_commutative=False)

class SegmentTree(object):

	def __init__(self, arg, sparse=False, ops=RangeOperators(), **kwarg):
		super(SegmentTree, self).__init__(**kwarg)
		try:
			init = list(arg)
			dim = len(init)
		except TypeError:
			init = None
			dim = arg
		self.dim = dim
		self.ops = ops
		self._lazy = self.ops.u_distributive is not None
		self._clean = True
		if sparse:
			self._tree = collections.defaultdict(ops.new)

			@functools.lru_cache(maxsize=dim)
			def seglen(u):
				if u >= self.dim:
					return 1
				return seglen(u << 1) + seglen(u << 1 | 1)
			self._seglen = seglen
			if self._lazy:
				self._pending = collections.defaultdict(lambda : None)
		else:
			self._tree = [ops.new() for _ in range(dim * 2)]
			seglen_precomp = [1] * dim * 2
			for u in reversed(range(1, dim)):
				seglen_precomp[u] = seglen_precomp[u << 1] + seglen_precomp[u << 1 | 1]
			self._seglen = seglen_precomp.__getitem__
			if self._lazy:
				self._pending = [None] * dim
		if init:
			self.update_consecutive_points(0, dim, init)

	def _downward_path(self, i):
		u = self.dim + i
		for s in range(u.bit_length() - 1, 0, -1):
			yield (u >> s)

	def _upward_path(self, i):
		u = self.dim + i
		while u > 1:
			u >>= 1
			yield u

	def _downward_fill(self, i, j):
		n = self.dim
		l = n + i
		r = n + j - 1
		for s in range(l.bit_length() - 1, 0, -1):
			for u in range(l >> s, (r >> s) + 1):
				yield u

	def _upward_fill(self, i, j):
		n = self.dim
		l = n + i
		r = n + j - 1
		while l > 1:
			l >>= 1
			r >>= 1
			for u in reversed(range(l, r + 1)):
				yield u

	def _cover_nodes(self, i, j):
		n = self.dim
		l = n + i
		r = n + j
		while l < r:
			if l & 1:
				yield l
				l += 1
			if r & 1:
				r -= 1
				yield r
			l >>= 1
			r >>= 1

	def _lazy_update(self, u, value):
		self._tree[u] = self.ops.u_distributive(self._tree[u], value, self._seglen(u))
		if u < self.dim:
			self._clean = False
			if self._pending[u] is None:
				self._pending[u] = value
			else:
				self._pending[u] = self.ops.update(self._pending[u], value)

	def _push1(self, u):
		assert u < self.dim
		if self._clean:
			return
		value = self._pending[u]
		if value is not None:
			for v in (u << 1, u << 1 | 1):
				self._lazy_update(v, value)
			self._pending[u] = None

	def _build1(self, u):
		assert u < self.dim
		self._push1(u)
		self._tree[u] = self.ops.query(self._tree[u << 1], self._tree[u << 1 | 1])

	def _push_path(self, i):
		if self._clean:
			return
		for u in self._downward_path(i):
			self._push1(u)

	def _push_fill(self, i, j):
		if self._clean:
			return
		for u in self._downward_fill(i, j):
			self._push1(u)
		if j - i == self.dim:
			self._clean = True

	def _build_path(self, i):
		for u in self._upward_path(i):
			self._build1(u)

	def _build_fill(self, i, j):
		for u in self._upward_fill(i, j):
			self._build1(u)
		if j - i == self.dim:
			self._clean = True

	def update_consecutive_points(self, start, stop, iterable):
		assert 0 <= start < stop <= self.dim
		if not self.ops.u_commutative:
			self._push_fill(start, stop - 1)
		for (u, value) in zip(range(self.dim + start, self.dim + stop), iterable):
			self._tree[u] = self.ops.update(self._tree[u], value)
		self._build_fill(start, stop - 1)

	def query_range(self, start, stop):
		assert start < stop
		for i in {start, stop - 1}:
			self._push_path(i)
		node_values = (self._tree[u] for u in self._cover_nodes(start, stop))
		return functools.reduce(self.ops.query, node_values)

	def update_range(self, start, stop, value):
		assert start < stop
		if not self._lazy:
			self.update_consecutive_points(start, stop, itertools.repeat(value))
			return
		if not self.ops.u_commutative:
			for i in {start, stop - 1}:
				self._push_path(i)
		for u in self._cover_nodes(start, stop):
			self._lazy_update(u, value)
		for i in {start, stop - 1}:
			self._build_path(i)

	def query_point(self, i):
		return self.query_range(i, i + 1)

	def update_point(self, i, value):
		self.update_range(i, i + 1, value)

class FenwickTree(object):

	def __init__(self, *dim, **kwarg):
		sparse = kwarg.pop('sparse', False)
		super(FenwickTree, self).__init__(**kwarg)
		self.dim = dim
		self.d = len(dim)
		if sparse:
			self._tree = collections.defaultdict(int)
			if self.d > 1:
				self._tree_setitem = self._tree.__setitem__
				self._tree_getitem = self._tree.__getitem__
		else:
			self._tree = hyperlist(*dim, default_factory=int)
			if self.d > 1:
				self._tree_setitem = functools.partial(hyperlist_setitem, self._tree)
				self._tree_getitem = functools.partial(hyperlist_getitem, self._tree)
		if self.d == 1:
			self.iadd = self._iadd_1d
			self._getitem = self._getitem_1d
		else:
			self.iadd = self._iadd_dd
			self._getitem = self._getitem_dd

	def __setitem__(self, key, value):
		self.iadd(key, value - self[key])

	def __getitem__(self, key):
		return self._getitem(key)

	@staticmethod
	def _set_index_iter(i, n):
		if i == 0:
			yield 0
			return
		while True:
			yield i
			i += i & -i
			if i >= n:
				return

	@staticmethod
	def _get_index_iter(i, j):
		if i < 0:
			return
		if j < 0:
			yield (0, +1)
			j = 0
		while i > j:
			yield (i, +1)
			i &= i - 1
		while j > i:
			yield (j, -1)
			j &= j - 1

	def _iadd_1d(self, key, value):
		assert 0 <= key < self.dim[0]
		for i in self._set_index_iter(key, self.dim[0]):
			self._tree[i] += value

	def _iadd_dd(self, key, value):
		assert len(key) == self.d
		assert all((0 <= i < self.dim[dd] for (dd, i) in enumerate(key))), 'index out of range'
		index_iters = [self._set_index_iter(i, self.dim[dd]) for (dd, i) in enumerate(key)]
		for u in itertools.product(*index_iters):
			g = self._tree_getitem(u)
			self._tree_setitem(u, g + value)

	def _getitem_1d(self, key):
		if isinstance(key, slice):
			assert key.step is None
			(start, stop, _) = key.indices(self.dim[0])
			if stop < start:
				stop = start
			(i, j) = (stop - 1, start - 1)
		else:
			(i, j) = (key, key - 1)
		assert -1 <= j <= i < self.dim[0], 'index out of range'
		sigma = 0
		for (k, sign) in self._get_index_iter(i, j):
			sigma += sign * self._tree[k]
		return sigma

	def _getitem_dd(self, key):
		index_iters = []
		for (dd, k) in enumerate(key):
			if isinstance(k, slice):
				assert k.step is None
				(start, stop, _) = k.indices(self.dim[dd])
				if stop < start:
					stop = start
				itr = self._get_index_iter(stop - 1, start - 1)
			else:
				assert 0 <= k < self.dim[dd], 'index out of range'
				itr = self._get_index_iter(k, k - 1)
			index_iters.append(itr)
		assert len(index_iters) == self.d, 'mismatched key dimensions'
		sigma = 0
		for i_sign_pairs in itertools.product(*index_iters):
			(u, signs) = zip(*i_sign_pairs)
			sign = m.prod(signs)
			sigma += sign * self._tree_getitem(u)
		return sigma
import math as m

def binary_search_int(f, start, stop):
	assert start < stop
	(left, right) = (start, stop)
	while left < right:
		mid = (left + right) // 2
		if f(mid):
			right = mid
		else:
			left = mid + 1
	return right

def binary_search_float(f, left, right, rel_tol=1e-09, abs_tol=0.0):
	assert left <= right
	while not m.isclose(left, right, rel_tol=rel_tol, abs_tol=abs_tol):
		mid = (left + right) / 2
		if f(mid):
			right = mid
		else:
			left = mid
	return right

def ternary_search_int(f, start, stop):
	assert start < stop
	invphi2 = (3 - m.sqrt(5)) / 2
	(a, d) = (start, stop - 1)
	b = a + round(invphi2 * (d - a))
	c = b + m.ceil(invphi2 * (d - b))
	fb = f(b)
	fc = f(c)
	while True:
		if fb < fc:
			if c == d:
				return d
			a = b + 1
			(b, fb) = (c, fc)
			c = b + m.ceil(invphi2 * (d - b))
			fc = f(c)
		else:
			if a == b:
				return a
			d = c - 1
			(c, fc) = (b, fb)
			b = c - m.ceil(invphi2 * (c - a))
			fb = f(b)

def ternary_search_float(f, left, right, rel_tol=1e-09, abs_tol=0.0):
	assert left <= right
	invphi2 = (3 - m.sqrt(5)) / 2
	(a, d) = (left, right)
	b = a + invphi2 * (d - a)
	c = b + invphi2 * (d - b)
	fb = f(b)
	fc = f(c)
	while not m.isclose(a, d, rel_tol=rel_tol, abs_tol=abs_tol):
		if fb < fc:
			a = b
			(b, fb) = (c, fc)
			c = b + invphi2 * (d - b)
			fc = f(c)
		else:
			d = c
			(c, fc) = (b, fb)
			b = c - invphi2 * (c - a)
			fb = f(b)
	return c
if False:
	import doctest
	doctest.testmod()
import sys

def input(itr=iter(sys.stdin.readlines())):
	return next(itr).rstrip('\n\r')
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
setu_maxq = RangeOperators(new=int, query=max, q_inverse=None, update=lambda t, x: x, u_distributive=lambda t, x, w: x, u_commutative=False)
st = SegmentTree(A, ops=setu_maxq)
responses = []
for _ in range(Q):
	T = tuple(map(int, input().split()))
	if T[0] == 1:
		(_, X, V) = T
		st.update_point(X - 1, V)
	elif T[0] == 2:
		(_, L, R) = T
		responses.append(st.query_range(L - 1, R - 1 + 1))
	elif T[0] == 3:
		(_, X, V) = T

		def valid(j):
			return st.query_range(X - 1, j - 1 + 1) >= V
		j = binary_search_int(valid, X, N + 1)
		responses.append(j)
print(*responses, sep='\n')


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

class SegmentTree:

	def __init__(self, n, p, unit, f):
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [unit] * (2 * self.num)
		for i in range(n):
			self.seg[i + self.num] = p[i]
		for i in range(self.num - 1, 0, -1):
			self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])
		self.f = f
		self.unit = unit

	def update(self, i, x):
		i += self.num
		self.seg[i] = x
		while i:
			i >>= 1
			self.seg[i] = self.f(self.seg[i << 1], self.seg[(i << 1) + 1])

	def query(self, l, r):
		ansl = ansr = self.unit
		l += self.num
		r += self.num - 1
		if l == r:
			return self.seg[l]
		f = self.f
		while l < r:
			if l & 1:
				ansl = f(ansl, self.seg[l])
				l += 1
			if ~r & 1:
				ansr = f(self.seg[r], ansr)
				r -= 1
			l >>= 1
			r >>= 1
		if l == r:
			ansl = f(ansl, self.seg[l])
		return f(ansl, ansr)
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
f = lambda x, y: max(x, y)
seg = SegmentTree(n, a, 0, f)
for _ in range(q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		seg.update(a - 1, b)
	if t == 2:
		print(seg.query(a - 1, b))
	if t == 3:
		ng = a - 1
		ok = n + 1
		while ng + 1 != ok:
			mid = (ng + ok) // 2
			if seg.query(ng, mid) >= b:
				ok = mid
			else:
				ng = mid
		print(ok)


class SegmentTree:

	def __init__(self, n, op, e):
		self.n = n
		self.op = op
		self.e = e
		self.size = 1 << (self.n - 1).bit_length()
		self.tree = [self.e] * (self.size << 1)

	def built(self, array):
		for i in range(self.n):
			self.tree[self.size + i] = array[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.op(self.tree[i << 1], self.tree[i << 1 | 1])

	def update(self, i, x):
		i += self.size
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = self.op(self.tree[i << 1], self.tree[i << 1 | 1])

	def get(self, l, r):
		l += self.size
		r += self.size
		res_l = self.e
		res_r = self.e
		while l < r:
			if l & 1:
				res_l = self.op(res_l, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res_r = self.op(self.tree[r], res_r)
			l >>= 1
			r >>= 1
		return self.op(res_l, res_r)

	def max_right(self, l, f):
		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.tree[l])):
				while l < self.size:
					l = 2 * l
					if f(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, f):
		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.tree[r], sm)):
				while r < self.size:
					r = 2 * r + 1
					if f(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 __iter__(self):
		for a in self.tree[self.size:self.size + self.n]:
			yield a

	def __str__(self):
		return str(self.tree[self.size:self.size + self.n])
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
e = 0
op = lambda x, y: x if x > y else y
st = SegmentTree(N, op, e)
st.built(A)
res = []
for _ in range(Q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		st.update(x - 1, y)
	elif t == 2:
		res.append(st.get(x - 1, y))
	else:
		res.append(st.max_right(x - 1, lambda z: z < y) + 1)
print('\n'.join(map(str, res)))


class RMaxQ:
	__slots__ = ['n', 'data', 'id']

	def __init__(self, li):
		self.n = len(li)
		self.id = -float('inf')
		self.data = [self.id] * self.n + li
		for i in range(self.n - 1, 0, -1):
			self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])

	def get(self, i):
		return self.data[i + self.n]

	def update(self, i, a):
		i += self.n
		self.data[i] = a
		while i > 1:
			i //= 2
			self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])

	def add(self, i, a):
		i += self.n
		self.data[i] += a
		while i > 1:
			i //= 2
			self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])

	def fold(self, l, r):
		l += self.n
		r += self.n
		res = self.id
		while l < r:
			if l % 2:
				res = max(self.data[l], res)
				l += 1
			if r % 2:
				r -= 1
				res = max(res, self.data[r])
			l //= 2
			r //= 2
		return res

	def max_right(self, l, r, check):
		l += self.n
		r += self.n
		left_li = []
		right_li = []
		while l < r:
			if l % 2:
				left_li.append(l)
				l += 1
			if r % 2:
				r -= 1
				right_li.append(r)
			l //= 2
			r //= 2
		temp = self.id
		for idx in left_li + right_li[::-1]:
			if not check(max(temp, self.data[idx])):
				temp = max(temp, self.data[idx])
			else:
				break
		else:
			return -1
		while idx < self.n:
			if check(max(temp, self.data[2 * idx])):
				idx = 2 * idx
			else:
				temp = max(temp, self.data[2 * idx])
				idx = 2 * idx + 1
		return idx - self.n

	def min_left(self, l, r, check):
		l += self.n
		r += self.n
		left_li = []
		right_li = []
		while l < r:
			if l % 2:
				left_li.append(l)
				l += 1
			if r % 2:
				r -= 1
				right_li.append(r)
			l //= 2
			r //= 2
		temp = self.id
		for idx in right_li + left_li[::-1]:
			if not check(max(self.data[idx], temp)):
				temp = max(self.data[idx], temp)
			else:
				break
		else:
			return -1
		while idx < self.n:
			if check(max(self.data[2 * idx + 1], temp)):
				idx = 2 * idx + 1
			else:
				temp = max(temp, self.data[2 * idx + 1], temp)
				idx = 2 * idx
		return idx - self.n
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
	(t, x, v) = map(int, input().split())
	x -= 1
	if t == 1:
		seg.update(x, v)
	elif t == 2:
		print(seg.fold(x, v))
	else:
		ans = seg.max_right(x, n, lambda x: x >= v)
		if ans == -1:
			print(n + 1)
		else:
			print(ans + 1)


class RMaxQ:
	__slots__ = ['n', 'data']

	def __init__(self, li):
		self.n = len(li)
		self.data = li * 2
		for i in range(self.n - 1, 0, -1):
			self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])

	def update(self, i, a):
		i += self.n
		self.data[i] = a
		while i > 1:
			i //= 2
			self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])

	def add(self, i, a):
		i += self.n
		self.data[i] += a
		while i > 1:
			i //= 2
			self.data[i] = max(self.data[2 * i], self.data[2 * i + 1])

	def fold(self, l, r):
		l += self.n
		r += self.n
		res = 0
		while l < r:
			if l % 2:
				res = max(self.data[l], res)
				l += 1
			if r % 2:
				r -= 1
				res = max(res, self.data[r])
			l //= 2
			r //= 2
		return res
import sys
input = sys.stdin.buffer.readline
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
seg = RMaxQ(A)
for _ in range(q):
	(t, x, v) = map(int, input().split())
	x -= 1
	if t == 1:
		seg.update(x, v)
	elif t == 2:
		print(seg.fold(x, v))
	else:
		ng = x
		ok = n + 1
		while ok - ng > 1:
			mid = (ok + ng) // 2
			if seg.fold(x, mid) >= v:
				ok = mid
			else:
				ng = mid
		print(ok)


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

class SegmentTree:

	def __init__(self, n, a=None):
		num = 1
		while num <= n:
			num <<= 1
		self.num = num
		self.seg = [0] * (2 * self.num - 1)
		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] = max(self.seg[(k << 1) + 1], self.seg[(k << 1) + 2])

	def update(self, i, x):
		k = i + (self.num - 1)
		self.seg[k] = x
		k = k - 1 >> 1
		while k >= 0:
			self.seg[k] = max(self.seg[(k << 1) + 1], self.seg[(k << 1) + 2])
			k = k - 1 >> 1

	def query(self, a, b):
		return self._query(a, b, 0, 0, self.num)

	def _query(self, a, b, k=0, l=0, r=None):
		if r is None:
			r = self.num
		if r <= a or b <= l:
			return -float('inf')
		elif a <= l and r <= b:
			return self.seg[k]
		else:
			return max(self._query(a, b, (k << 1) + 1, l, l + r >> 1), self._query(a, b, (k << 1) + 2, l + r >> 1, r))

	def find_right(self, a, b, x):
		return self._find_right(a, b, x, k=0, l=0, r=self.num)

	def _find_right(self, a, b, x, k, l, r):
		if self.seg[k] < x or r <= a or b <= l:
			return -1
		elif k >= self.num - 1:
			return k - (self.num - 1)
		else:
			vr = self._find_right(a, b, x, (k << 1) + 2, l + r >> 1, r)
			if vr >= 0:
				return vr
			else:
				return self._find_right(a, b, x, (k << 1) + 1, l, l + r >> 1)

	def find_left(self, a, b, x):
		return self._find_left(a, b, x, k=0, l=0, r=self.num)

	def _find_left(self, a, b, x, k, l, r):
		if self.seg[k] < x or r <= a or b <= l:
			return self.num
		elif k >= self.num - 1:
			return k - (self.num - 1)
		else:
			vl = self._find_left(a, b, x, (k << 1) + 1, l, l + r >> 1)
			if vl < self.num:
				return vl
			else:
				return self._find_left(a, b, x, (k << 1) + 2, l + r >> 1, r)

	def query_index(self, a, b, k=0, l=0, r=None):
		if r is None:
			r = self.num
		if r <= a or b <= l:
			return (-float('inf'), None)
		elif a <= l and r <= b:
			return (self.seg[k], self._index(k))
		else:
			return max(self.query_index(a, b, (k << 1) + 1, l, l + r >> 1), self.query_index(a, b, (k << 1) + 2, l + r >> 1, r))

	def _index(self, k):
		if k >= self.num:
			return k - (self.num - 1)
		elif self.seg[(k << 1) + 1] >= self.seg[(k << 1) + 2]:
			return self._index((k << 1) + 1)
		else:
			return self._index((k << 1) + 2)
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		sg.update(x - 1, y)
	elif t == 2:
		print(sg.query(x - 1, y))
	else:
		res = sg.find_left(x - 1, n, y) + 1
		if res >= n + 1:
			print(n + 1)
		else:
			print(res)


from typing import Callable, List, TypeVar
T = TypeVar('T')

class SegmentTree:
	__slots__ = ['e', 'op', '_n', '_size', 'tree']

	def __init__(self, a: List[T], e: T, op: Callable[[T, T], T]) -> None:
		self.e = e
		self.op = op
		self._n = len(a)
		self._size = 1 << (self._n - 1).bit_length()
		self.tree = [e] * self._size + a + [e] * (self._size - self._n)
		for i in range(self._size - 1, 0, -1):
			self._update(i)

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

	def set(self, k: int, x: T) -> None:
		assert 0 <= k < self._n
		k += self._size
		self.tree[k] = x
		while k:
			k >>= 1
			self._update(k)

	def get(self, k: int) -> T:
		assert 0 <= k < self._n
		return self.tree[k + self._size]

	def prod(self, l: int, r: int) -> T:
		assert 0 <= l <= r <= self._n
		(sml, smr) = (self.e, self.e)
		l += self._size
		r += self._size
		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) -> T:
		return self.tree[1]

	def max_right(self, l: int, f: Callable[[T], bool]) -> int:
		assert 0 <= l <= self._n
		assert f(self.e)
		if l == self._n:
			return self._n
		l += self._size
		sm = self.e
		while True:
			while not l & 1:
				l >>= 1
			if not f(self.op(sm, self.tree[l])):
				while l < self._size:
					l *= 2
					if f(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, f: Callable[[T], bool]) -> int:
		assert 0 <= r <= self._n
		assert f(self.e)
		if not r:
			return 0
		r += self._size
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not f(self.op(self.tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if f(self.op(self.tree[r], sm)):
						sm = self.op(self.tree[r], sm)
						r -= 1
				return r + 1 - self._size
			if r & -r == r:
				break
		return 0

def practice2_j():
	(N, _, *AQ) = map(int, open(0).read().split())
	(A, Q) = (AQ[:N], AQ[N:])
	tree = SegmentTree(A, -1, max)
	res = []
	for (t, x, y) in zip(*[iter(Q)] * 3):
		if t == 1:
			tree.set(x - 1, y)
		elif t == 2:
			res.append(tree.prod(x - 1, y))
		else:
			res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
	print('\n'.join(map(str, res)))

def staticrmq():
	(N, Q, *ALR) = map(int, open(0).read().split())
	(A, LR) = (ALR[:N], ALR[N:])
	tree = SegmentTree(A, 10 ** 10 + 1, min)
	res = [tree.prod(l, r) for (l, r) in zip(*[iter(LR)] * 2)]
	print('\n'.join(map(str, res)))

def dsl_2_a():
	(N, Q, *X) = map(int, open(0).read().split())
	tree = SegmentTree([2 ** 31 - 1] * N, 2 ** 31 - 1, min)
	res = []
	for (com, x, y) in zip(*[iter(X)] * 3):
		if com:
			res.append(tree.prod(x, y + 1))
		else:
			tree.set(x, y)
	print('\n'.join(map(str, res)))

def abc125_c():
	from math import gcd
	(N, *A) = map(int, open(0).read().split())
	tree = SegmentTree(A, 0, gcd)
	res = max((gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N)))
	print(res)
practice2_j()


class SegmentTree:

	def __init__(self, list, f=lambda x, y: x + y, inf=0):
		self.height = (len(list) - 1).bit_length() + 1
		self.zero = 2 ** (self.height - 1)
		self.id = inf
		self.tree = [self.id] * 2 ** self.height
		self.f = f
		for i in range(len(list)):
			self.tree[self.zero + i] = list[i]
		for i in range(self.zero - 1, 0, -1):
			self.tree[i] = self.f(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, i, x):
		i += self.zero
		self.tree[i] = x
		while i > 1:
			i //= 2
			self.tree[i] = self.f(self.tree[2 * i], self.tree[2 * i + 1])

	def query(self, l, r):
		l += self.zero
		r += self.zero
		(lf, rf) = (self.id, self.id)
		while l < r:
			if l & 1:
				lf = self.f(lf, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				rf = self.f(self.tree[r], rf)
			l //= 2
			r //= 2
		return self.f(lf, rf)

	def BinarySearch(self, l, r, f):
		if not f(self.query(l, r)):
			return r + 1
		l += self.zero
		r += self.zero
		while True:
			if f(self.tree[l]):
				if l >= self.zero:
					return l - self.zero + 1
				else:
					l *= 2
			elif l % 2 == 0:
				l += 1
			else:
				l = l // 2 + 1
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
seg = SegmentTree(a, max)
for i in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		seg.update(x - 1, y)
	elif t == 2:
		print(seg.query(x - 1, y))
	else:
		print(seg.BinarySearch(x - 1, n, lambda x: x >= y))


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
seg_el = 1 << N.bit_length()
SEG = [0] * (2 * seg_el)
for i in range(N):
	SEG[i + seg_el] = A[i]
for i in range(seg_el - 1, 0, -1):
	SEG[i] = max(SEG[i * 2], SEG[i * 2 + 1])

def update(n, x, seg_el):
	i = n + seg_el
	SEG[i] = x
	i >>= 1
	while i != 0:
		SEG[i] = max(SEG[i * 2], SEG[i * 2 + 1])
		i >>= 1

def getvalues(l, r):
	L = l + seg_el
	R = r + seg_el
	ANS = 0
	while L < R:
		if L & 1:
			ANS = max(ANS, SEG[L])
			L += 1
		if R & 1:
			R -= 1
			ANS = max(ANS, SEG[R])
		L >>= 1
		R >>= 1
	return ANS

def bisect_on_SEG(l, x):
	L = l + seg_el
	R = seg_el * 2 - 1
	while L < R:
		if SEG[L] >= x:
			break
		if L & 1:
			L += 1
		L >>= 1
		R >>= 1
	if SEG[L] < x:
		return N
	while L < seg_el:
		if SEG[L * 2] >= x:
			L = L * 2
		else:
			L = L * 2 + 1
	return L - seg_el
for queries in range(Q):
	(T, X, V) = map(int, input().split())
	if T == 1:
		update(X - 1, V, seg_el)
	elif T == 2:
		print(getvalues(X - 1, V))
	else:
		print(1 + bisect_on_SEG(X - 1, V))


import sys
sys.setrecursionlimit(10 ** 7)

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

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

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

class SegTree:

	def __init__(self, N, seg_func, unit):
		self.N = 1 << (N - 1).bit_length()
		self.func = seg_func
		self.unit = unit
		self.tree = [self.unit] * (2 * self.N)

	def build(self, init_value):
		for i in range(len(init_value)):
			self.tree[i + self.N] = init_value[i]
		for i in range(self.N - 1, 0, -1):
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

	def set_val(self, i, x):
		i += self.N
		self.tree[i] = x
		i >>= 1
		while i:
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])
			i >>= 1

	def fold(self, L, R):
		L += self.N
		R += self.N
		vL = self.unit
		vR = self.unit
		while L < R:
			if L & 1:
				vL = self.func(vL, self.tree[L])
				L += 1
			if R & 1:
				R -= 1
				vR = self.func(self.tree[R], vR)
			L >>= 1
			R >>= 1
		return self.func(vL, vR)

	def max_right(self, l, z):
		if l >= self.N:
			return self.N
		l += self.N
		s = self.unit
		while True:
			while l % 2 == 0:
				l >>= 1
			if not z(self.func(s, self.tree[l])):
				while l < self.N:
					l *= 2
					if z(self.func(s, self.tree[l])):
						s = self.func(s, self.tree[l])
						l += 1
				return l - self.N
			s = self.func(s, self.tree[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.unit
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not z(self.func(self.tree[r], s)):
				while r < self.N:
					r = r * 2 + 1
					if z(self.func(self.tree[r], s)):
						s = self.func(self.tree[r], s)
						r -= 1
				return r + 1 - self.N
			s = self.func(self.tree[r], s)
			if r & -r == r:
				break
		return 0

def seg_func(x, y):
	return max(x, y)
unit = 0
(N, Q) = MI()
A = LI()
ST = SegTree(N, seg_func, unit)
ST.build(A)
for _ in range(Q):
	(t, a, b) = MI()
	if t == 1:
		ST.set_val(a - 1, b)
	elif t == 2:
		print(ST.fold(a - 1, b))
	else:

		def z(x):
			return x < b
		print(min(ST.max_right(a - 1, z), N) + 1)


class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.range = [(-1, n)] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
			self.range[self.num + i] = (i, i)
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
			self.range[i] = (self.range[2 * i][0], self.range[2 * i + 1][1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] >= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] >= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] >= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] >= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return N
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
Seg = SegmentTree(A, max, 0)
for _ in range(Q):
	query = list(map(int, input().split()))
	if query[0] == 1:
		(gomi, idx, val) = query
		Seg.update(idx - 1, val)
	elif query[0] == 2:
		(gomi, l, r) = query
		print(Seg.query(l - 1, r))
	else:
		(gomi, l, val) = query
		print(Seg.bisect_l(l - 1, N, val) + 1)


class Segment_Tree:

	def __init__(self, N, calc, unit, L=[]):
		self.calc = calc
		self.unit = unit
		N = max(N, len(L))
		d = max(1, (N - 1).bit_length())
		k = 2 ** d
		X = [unit] * (k - 1) + L + [unit] * (k - len(L))
		self.num = k
		self.depth = d
		for i in range(k - 2, -1, -1):
			X[i] = calc(X[2 * i + 1], X[2 * i + 2])
		self.data = X

	def index(self, k, index=0):
		return self.data[self.num - 1 + (k - index)]

	def update(self, k, x, index=0):
		m = self.num - 1 + (k - index)
		self.data[m] = x
		for _ in range(self.depth):
			m = (m - 1) // 2
			self.data[m] = self.calc(self.data[2 * m + 1], self.data[2 * m + 2])

	def sub_array(self, From, To, index=0, left_closed=True, right_closed=True):
		A = From - index + (not left_closed)
		B = To - index - (not right_closed)
		return self.__sub_array_second(A, B + 1, 0, 0, self.num)

	def __sub_array_second(self, a, b, k, l, r):
		if r <= a or b <= l:
			return self.unit
		elif a <= l and r <= b:
			return self.data[k]
		else:
			alpha = self.__sub_array_second(a, b, 2 * k + 1, l, (l + r) // 2)
			beta = self.__sub_array_second(a, b, 2 * k + 2, (l + r) // 2, r)
			return self.calc(alpha, beta)

	def all_prod(self):
		return self.data[0]

	def max_right(self, l, r, cond, index=0):
		l -= index
		if l == r:
			return r + index
		l += self.num - 1
		sm = self.unit
		calc = self.calc
		while True:
			while l % 2:
				l = l - 1 >> 1
			if not cond(calc(sm, self.data[l])):
				while l < self.num - 1:
					l = 2 * l + 1
					if cond(calc(sm, self.data[l])):
						sm = calc(sm, self.data[l])
						l += 1
				return min(l - (self.num - 1) + index, r)
			sm = calc(sm, self.data[l])
			l += 1
			m = l + 1
			if not m & -m != m:
				break
		return r + index
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
S = Segment_Tree(N, lambda x, y: max(x, y), 0, A)
X = []
for _ in range(Q):
	(T, alpha, beta) = map(int, input().split())
	if T == 1:
		S.update(alpha, beta, 1)
	elif T == 2:
		X.append(S.sub_array(alpha, beta, 1))
	else:
		X.append(S.max_right(alpha, N, lambda x: x < beta, 1))
print('\n'.join(map(str, X)))


def solve():

	def segfunc(x, y):
		return max(x, y)

	def init(init_val):
		for i in range(n):
			seg[i + num - 1] = init_val[i]
		for i in range(num - 2, -1, -1):
			seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

	def update(k, x):
		k += num - 1
		seg[k] = x
		while k:
			k = (k - 1) // 2
			seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

	def query(p, q):
		if q <= p:
			return ide_ele
		p += num - 1
		q += num - 2
		res = ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = segfunc(res, seg[p])
			if q & 1 == 1:
				res = segfunc(res, seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = segfunc(res, seg[p])
		else:
			res = segfunc(segfunc(res, seg[p]), seg[q])
		return res
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	ide_ele = 0
	num = 2 ** (n - 1).bit_length()
	seg = [ide_ele] * 2 * num
	init(a)
	for _ in range(q):
		(t, a, b) = map(int, input().split())
		if t == 1:
			update(a - 1, b)
		elif t == 2:
			print(query(a - 1, b))
		elif t == 3:
			ng = a - 1
			ok = n + 1
			while ok > ng + 1:
				mid = (ok + ng) // 2
				if query(ng, mid) >= b:
					ok = mid
				else:
					ng = mid
			print(ok)
solve()


class SegmentTree:
	__slots__ = ['func', 'e', 'original_size', 'n', 'data']

	def __init__(self, length_or_list, func, e):
		self.func = func
		self.e = e
		if isinstance(length_or_list, int):
			self.original_size = length_or_list
			self.n = 1 << (length_or_list - 1).bit_length()
			self.data = [self.e] * self.n
		else:
			self.original_size = len(length_or_list)
			self.n = 1 << (self.original_size - 1).bit_length()
			self.data = [self.e] * self.n + length_or_list + [self.e] * (self.n - self.original_size)
			for i in range(self.n - 1, 0, -1):
				self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def replace(self, index, value):
		index += self.n
		self.data[index] = value
		index //= 2
		while index > 0:
			self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
			index //= 2

	def folded(self, l, r):
		left_folded = self.e
		right_folded = self.e
		l += self.n
		r += self.n
		while l < r:
			if l % 2:
				left_folded = self.func(left_folded, self.data[l])
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.func(self.data[r], right_folded)
			l //= 2
			r //= 2
		return self.func(left_folded, right_folded)

	def all_folded(self):
		return self.data[1]

	def __getitem__(self, index):
		return self.data[self.n + index]

	def max_right(self, l, f):
		if l >= self.original_size:
			return self.original_size
		l += self.n
		left_folded = self.e
		while True:
			while l % 2 == 0:
				l //= 2
			if not f(self.func(left_folded, self.data[l])):
				while l < self.n:
					l *= 2
					if f(self.func(left_folded, self.data[l])):
						left_folded = self.func(left_folded, self.data[l])
						l += 1
				return l - self.n
			left_folded = self.func(left_folded, self.data[l])
			l += 1
			if l == l & -l:
				break
		return self.original_size

	def min_left(self, r, f):
		if r == 0:
			return 0
		r += self.n
		right_folded = self.e
		while True:
			r //= r & -r
			if not f(self.func(self.data[r], right_folded)):
				while r < self.n:
					r = 2 * r + 1
					if f(self.func(self.data[r], right_folded)):
						right_folded = self.func(self.data[r], right_folded)
						r -= 1
				return r + 1 - self.n
			if r == r & -r:
				break
		return 0

def yosupo():
	import sys
	input = sys.stdin.buffer.readline
	read = sys.stdin.buffer.read
	(N, Q) = map(int, input().split())
	seg = SegmentTree(list(map(int, input().split())), lambda a, b: a + b, 0)
	for _ in range(Q):
		(a, b, c) = map(int, input().split())
		if a:
			print(seg.folded(b, c))
		else:
			seg.replace(b, seg[b] + c)

def aoj():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	seg = SegmentTree([2 ** 31 - 1] * N, min, 2 ** 31 - 1)
	for _ in range(Q):
		(q, x, y) = map(int, input().split())
		if q == 0:
			seg.replace(x, y)
		else:
			print(seg.folded(x, y + 1))

def main():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	As = list(map(int, input().split()))
	seg = SegmentTree(As, max, 0)
	for _ in range(Q):
		(T, X, V) = map(int, input().split())
		if T == 1:
			seg.replace(X - 1, V)
		elif T == 2:
			print(seg.folded(X - 1, V))
		else:
			print(seg.max_right(X - 1, lambda a: a < V) + 1)
main()


class SegmentTree:

	def __init__(self, n, f=max, default=-10 ** 18):
		self.num_leaf = 1
		while self.num_leaf < n:
			self.num_leaf *= 2
		self.data = [default] * (2 * self.num_leaf)
		self.f = f

	def 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 query(self, l, r):
		l += self.num_leaf
		r += self.num_leaf - 1
		(lres, rres) = (self.data[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

	def lower_bound_index(self, x, v):
		x += self.num_leaf
		while self.data[x] < v:
			if x & 1:
				if len(bin(x)) == len(bin(x + 1)):
					x += 1
				else:
					return self.num_leaf
			else:
				x >>= 1
		while x < self.num_leaf:
			if self.data[2 * x] >= v:
				x = 2 * x
			else:
				x = 2 * x + 1
		return x - self.num_leaf

def main():
	from sys import stdin
	input = stdin.buffer.readline
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	st = SegmentTree(n=n, f=max, default=-1)
	for (i, ai) in enumerate(a):
		st.update(i, ai)
	ans = []
	for _ in range(q):
		(t, x, v) = map(int, input().split())
		if t == 1:
			st.update(x - 1, v)
		elif t == 2:
			ans.append(st.query(x - 1, v))
		else:
			ans.append(min(st.lower_bound_index(x - 1, v), n) + 1)
	for i in ans:
		print(i)
main()


class SegTree:

	def __init__(self, a, func, idem):
		self.n = 1 << len(a).bit_length()
		self.size = len(a)
		self.func = func
		self.idem = idem
		self.node = [idem] * (2 * self.n - 1)
		for i in range(len(a) + self.n - 2, -1, -1):
			if i >= self.n - 1:
				self.node[i] = a[i - self.n + 1]
			else:
				self.node[i] = self.func(self.node[2 * i + 1], self.node[2 * i + 2])

	def get(self, x):
		return self.node[x + self.n - 1]

	def set(self, x, val):
		x += self.n - 1
		self.node[x] = val
		while x > 0:
			x = x - 1 >> 1
			self.node[x] = self.func(self.node[2 * x + 1], self.node[2 * x + 2])
		return

	def prod(self, l, r):
		(L, R) = (l + self.n, r + self.n)
		(s_l, s_r) = (self.idem, self.idem)
		while L < R:
			if R & 1:
				R -= 1
				s_r = self.func(self.node[R - 1], s_r)
			if L & 1:
				s_l = s_l = self.func(s_l, self.node[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return self.func(s_l, s_r)

	def max_right(self, l, val):
		if l == self.size:
			return self.size
		L = l + self.n
		s = self.idem
		while 1:
			while L % 2 == 0:
				L >>= 1
			if not val(self.func(s, self.node[L - 1])):
				while L < self.n:
					L <<= 1
					if val(self.func(s, self.node[L - 1])):
						s = self.func(s, self.node[L - 1])
						L += 1
				return L - self.n
			s = self.func(s, self.node[L - 1])
			L += 1
			if L & -L == L:
				return self.size

	def min_left(self, r, val):
		if r == 0:
			return 0
		R = r + self.n
		s = self.idem
		while True:
			R -= 1
			while R > 1 and R % 2:
				R >>= 1
			if not val(self.func(self.node[R - 1], s)):
				while R < self.n:
					R = (R << 1) + 1
					if val(self.func(self.node[R - 1], s)):
						s = self.func(self.node[R - 1], s)
						R -= 1
				return R + 1 - self.n
			s = self.func(self.node[R - 1], s)
			if R & -R == R:
				return 0
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
st = SegTree(A, max, 0)
for _ in range(Q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		st.set(x - 1, y)
	elif t == 2:
		print(st.prod(x - 1, y))
	else:
		print(st.max_right(x - 1, lambda z: z < y) + 1)


from typing import Callable, TypeVar, List
import sys
input = sys.stdin.readline
T = TypeVar('T')

class SegTree:

	def __init__(self, v: List[T], op: Callable[[T, T], T], e: Callable[[], T]) -> None:
		self._n = len(v)
		self.log = (self._n - 1).bit_length()
		self.size = 1 << self.log
		self.d = [e() for _ in range(2 * self.size)]
		self.op = op
		self.e = e
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in reversed(range(1, self.size)):
			self.d[i] = self.op(self.d[2 * i], self.d[2 * i + 1])

	@classmethod
	def init_e(cls, n: int, op: Callable[[T, T], T], e: Callable[[], T]) -> 'SegTree':
		return cls([e for _ in range(n)], op, e)

	def set(self, p: int, x: T) -> None:
		assert 0 <= p < self._n
		p += self.size
		self.d[p] = x
		for i in range(1, self.log + 1):
			k = p >> i
			self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

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

	def prod(self, l: int, r: int) -> T:
		assert 0 <= l <= self._n and 0 <= r <= self._n
		sml = self.e()
		smr = self.e()
		l += self.size
		r += self.size
		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) -> T:
		return self.d[1]

	def max_right(self, l: int, f: Callable[[T], bool]):
		assert 0 <= 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
					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:
				return self._n

	def min_left(self, r: int, f: Callable[[T], bool]):
		assert 0 <= 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:
				return 0

	def __update__(self, k: int) -> None:
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
seg = SegTree(a, max, lambda : -1)
for _ in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		seg.set(x - 1, y)
	elif t == 2:
		print(seg.prod(x - 1, y))
	else:
		print(seg.max_right(x - 1, lambda v: v < y) + 1)


import sys
input = sys.stdin.readline

class segtree:
	x_unit = 0
	x_func = max
	condition = lambda self, a, b: a >= b

	def __init__(self, n, seq):
		self.n = n
		self.x = [self.x_unit] * (2 * n)
		for (i, j) in enumerate(seq, self.n):
			self.x[i] = j
		for i in range(self.n - 1, 0, -1):
			self.x[i] = self.x_func(self.x[i * 2], self.x[i * 2 + 1])

	def update(self, i, j):
		i += self.n
		self.x[i] = j
		while i > 1:
			i //= 2
			self.x[i] = self.x_func(self.x[i * 2], self.x[i * 2 + 1])

	def get(self, i):
		return self.x[i + self.n]

	def fold(self, l, r):
		l += self.n
		r += self.n
		val_l = self.x_unit
		val_r = self.x_unit
		while l < r:
			if l & 1:
				val_l = self.x_func(val_l, self.x[l])
				l += 1
			if r & 1:
				r -= 1
				val_r = self.x_func(val_r, self.x[r])
			l //= 2
			r //= 2
		return self.x_func(val_l, val_r)

	def max_right(self, l, v):
		r = self.n
		if self.condition(self.fold(l, r), v) == False:
			return r
		else:
			while r - l > 1:
				l1 = l
				r1 = l + (r - l) // 2
				l2 = l + (r - l) // 2
				r2 = r
				if self.condition(self.fold(l1, r1), v) == True:
					l = l1
					r = r1
				else:
					l = l2
					r = r2
			return l

	def min_left(self, r, v):
		l = 0
		if self.condition(self.fold(l, r), v) == False:
			return l
		else:
			while r - l > 1:
				l1 = l
				r1 = l + (r - l) // 2
				l2 = l + (r - l) // 2
				r2 = r
				if self.condition(self.fold(l1, r1), v) == True:
					l = l1
					r = r1
				else:
					l = l2
					r = r2
			return r
(n, q) = map(int, input().split())
(*a,) = map(int, input().split())
seg = segtree(n, a)
for i in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		x -= 1
		seg.update(x, y)
	elif t == 2:
		print(seg.fold(x - 1, y))
	else:
		print(seg.max_right(x - 1, y) + 1)


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

class SegmentTree:

	def __init__(self, n, a=None):
		num = 1
		while num <= n:
			num *= 2
		self.num = num
		self.seg = [ninf] * (2 * self.num - 1)
		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] = max(self.seg[2 * k + 1], self.seg[2 * k + 2])

	def update(self, i, x):
		k = i + (self.num - 1)
		self.seg[k] = x
		k = (k - 1) // 2
		while k >= 0:
			self.seg[k] = max(self.seg[2 * k + 1], self.seg[2 * k + 2])
			k = (k - 1) // 2

	def query(self, a, b):
		k = 0
		l = 0
		r = self.num
		q = [(k, l, r)]
		ans = ninf
		while q:
			(k, l, r) = q.pop()
			if r <= a or b <= l:
				pass
			elif a <= l and r <= b:
				ans = max(ans, self.seg[k])
			else:
				q.append((2 * k + 1, l, (l + r) // 2))
				q.append((2 * k + 2, (l + r) // 2, r))
		return ans

	def find_right(self, a, b, x):
		k = 0
		l = 0
		r = self.num
		q = [(k, l, r, True)]
		ans = -1
		while q:
			(k, l, r, flg) = q.pop()
			if flg:
				if self.seg[k] > x or r <= a or b <= l:
					pass
				elif k >= self.num - 1:
					ans = max(ans, k - (self.num - 1))
					return ans
				else:
					q.append((2 * k + 1, l, (l + r) // 2, True))
					q.append((2 * k + 2, (l + r) // 2, r, False))
			else:
				if ans < self.num:
					return ans
				q.append((k, l, r, True))
		return ans

	def find_left(self, a, b, x):
		k = 0
		l = 0
		r = self.num
		q = [(k, l, r, True)]
		ans = self.num
		while q:
			(k, l, r, flg) = q.pop()
			if flg:
				if self.seg[k] < x or r <= a or b <= l:
					continue
				elif k >= self.num - 1:
					ans = min(ans, k - (self.num - 1))
					return ans
				else:
					q.append((2 * k + 2, (l + r) // 2, r, False))
					q.append((2 * k + 1, l, (l + r) // 2, True))
			else:
				if ans < self.num:
					return ans
				q.append((k, l, r, True))
		return ans

	def query_index(self, a, b, k=0, l=0, r=None):
		if r is None:
			r = self.num
		if r <= a or b <= l:
			return (ninf, None)
		elif a <= l and r <= b:
			return (self.seg[k], self._index(k))
		else:
			return max(self.query_index(a, b, 2 * k + 1, l, (l + r) // 2), self.query_index(a, b, 2 * k + 2, (l + r) // 2, r))

	def _index(self, k):
		if k >= self.num:
			return k - (self.num - 1)
		elif self.seg[2 * k + 1] >= self.seg[2 * k + 2]:
			return self._index(2 * k + 1)
		else:
			return self._index(2 * k + 2)
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
sg = SegmentTree(n, a)
for _ in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		sg.update(x - 1, y)
	elif t == 2:
		print(sg.query(x - 1, y))
	else:
		res = sg.find_left(x - 1, n, y) + 1
		if res >= n + 1:
			print(n + 1)
		else:
			print(res)


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def main():
	(N, Q) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]

	def segfunc(x, y):
		return max(x, y)

	class SegmentTree:

		def __init__(self, init_val, ide_ele):
			self.n = len(init_val)
			self.ide_ele = ide_ele
			self.num = 2 ** (self.n - 1).bit_length()
			self.seg = [self.ide_ele] * 2 * self.num
			for i in range(self.n):
				self.seg[i + self.num - 1] = init_val[i]
			for i in range(self.num - 2, -1, -1):
				self.seg[i] = segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

		def update(self, k, x):
			k += self.num - 1
			self.seg[k] = x
			while k:
				k = (k - 1) // 2
				self.seg[k] = segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

		def query(self, p, q):
			if q <= p:
				return self.ide_ele
			p += self.num - 1
			q += self.num - 2
			res = self.ide_ele
			while q - p > 1:
				if p & 1 == 0:
					res = segfunc(res, self.seg[p])
				if q & 1 == 1:
					res = segfunc(res, self.seg[q])
					q -= 1
				p = p // 2
				q = (q - 1) // 2
			if p == q:
				res = segfunc(res, self.seg[p])
			else:
				res = segfunc(segfunc(res, self.seg[p]), self.seg[q])
			return res
	s = SegmentTree(A, 0)

	def isOK(mid, m, value):
		a = s.query(m, mid)
		return a >= value
	B = A[:]
	for _ in range(Q):
		(T, X, V) = [int(x) for x in input().split()]
		if T == 1:
			s.update(X - 1, V)
			B[X - 1] = V
		elif T == 2:
			print(s.query(X - 1, V))
		else:
			a = s.query(X - 1, N)
			if a < V:
				print(N + 1)
			else:
				if B[X - 1] >= V:
					print(X)
					continue
				ok = N - 1
				ng = X - 1
				while abs(ok - ng) > 1:
					mid = (ok + ng) // 2
					if isOK(mid, X - 1, V):
						ok = mid
					else:
						ng = mid
				print(ok)
main()


class segment_tree:
	__slots__ = ['op_M', 'e_M', 'N', 'N0', 'dat']

	def __init__(self, N, operator_M, e_M):
		self.op_M = operator_M
		self.e_M = e_M
		self.N = N
		self.N0 = 1 << (N - 1).bit_length()
		self.dat = [self.e_M] * (2 * self.N0)

	def build(self, initial):
		self.dat[self.N0:self.N0 + len(initial)] = initial[:]
		for k in range(self.N0 - 1, 0, -1):
			self.dat[k] = self.op_M(self.dat[2 * k], self.dat[2 * k + 1])

	def update(self, k, x):
		k += self.N0
		self.dat[k] = x
		k >>= 1
		while k:
			self.dat[k] = self.op_M(self.dat[2 * k], self.dat[2 * k + 1])
			k >>= 1

	def query(self, L, R):
		L += self.N0
		R += self.N0 + 1
		sl = sr = self.e_M
		while L < R:
			if R & 1:
				R -= 1
				sr = self.op_M(self.dat[R], sr)
			if L & 1:
				sl = self.op_M(sl, self.dat[L])
				L += 1
			L >>= 1
			R >>= 1
		return self.op_M(sl, sr)

	def get(self, k):
		return self.dat[k + self.N0]

	def max_right(self, l, f):
		if l == self.N:
			return self.N
		l += self.N0
		sm = self.e_M
		while True:
			while l & 1 == 0:
				l >>= 1
			if not f(self.op_M(sm, self.dat[l])):
				while l < self.N0:
					l *= 2
					if f(self.op_M(sm, self.dat[l])):
						sm = self.op_M(sm, self.dat[l])
						l += 1
				return l - self.N0
			sm = self.op_M(sm, self.dat[l])
			l += 1
			if l & -l == l:
				break
		return self.N

	def min_left(self, r, f):
		if r == 0:
			return 0
		r += self.N0
		sm = self.e_M
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not f(self.op_M(self.dat[r], sm)):
				while r < self.N0:
					r = r * 2 + 1
					if f(self.op_M(self.dat[r], sm)):
						sm = self.op_M(self.dat[r], sm)
						r -= 1
				return r + 1 - self.N0
			sm = self.op_M(self.dat[r], sm)
			if r & -r == r:
				break
		return 0
import sys
readline = sys.stdin.readline
(n, q) = map(int, readline().split())
(*a,) = map(int, readline().split())
seg = segment_tree(n, max, 0)
seg.build(a)
for _ in range(q):
	(idx, p, v) = map(int, readline().split())
	if idx == 1:
		seg.update(p - 1, v)
	elif idx == 2:
		print(seg.query(p - 1, v - 1))
	else:
		print(seg.max_right(p - 1, lambda x: x < v) + 1)


class SegTree:

	def __init__(self, N, data_f=min, data_unit=1 << 30):
		self.N = N
		self.data_f = data_f
		self.data_unit = data_unit
		self.data = [self.data_unit] * (N + N)

	def build(self, raw_data):
		data = self.data
		f = self.data_f
		N = self.N
		data[N:] = raw_data[:]
		for i in range(N - 1, 0, -1):
			data[i] = f(data[i << 1], data[i << 1 | 1])

	def set_val(self, i, x):
		data = self.data
		f = self.data_f
		i += self.N
		data[i] = x
		while i > 1:
			data[i >> 1] = f(data[i], data[i ^ 1])
			i >>= 1

	def fold(self, L, R):
		vL = vR = self.data_unit
		data = self.data
		f = self.data_f
		L += self.N
		R += self.N
		while L < R:
			if L & 1:
				vL = f(vL, data[L])
				L += 1
			if R & 1:
				R -= 1
				vR = f(data[R], vR)
			L >>= 1
			R >>= 1
		return f(vL, vR)

	def search_left(self, f, L, R):
		if not f(self.fold(L, R)):
			return R
		while R - L > 1:
			M = (R + L) // 2
			if f(self.fold(L, M)):
				R = M
			else:
				L = M
		return L
(N, Q) = map(int, input().split())
(*A,) = map(int, input().split())
seg = SegTree(N, max, 0)
seg.build(A)
for i in range(Q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		seg.set_val(a - 1, b)
	elif t == 2:
		print(seg.fold(a - 1, b))
	else:
		print(seg.search_left(lambda x: x >= b, a - 1, N) + 1)


class segmentTree:

	def __init__(self, init_val, operator, identity):
		self.identity = identity
		self.operator = operator
		n = len(init_val)
		n_bin = bin(n)[2:]
		bc = sum([int(digit) for digit in n_bin])
		if bc == 1:
			self.num_end_leaves = 2 ** (len(n_bin) - 1)
		else:
			self.num_end_leaves = 2 ** len(n_bin)
		self.tree = [identity for _ in range(self.num_end_leaves * 2)]
		for i in range(n):
			self.tree[i + self.num_end_leaves] = init_val[i]
		for i in range(1, self.num_end_leaves)[::-1]:
			self.tree[i] = self.operator(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, x, val):
		leaf_x = x + self.num_end_leaves
		self.tree[leaf_x] = val
		while leaf_x > 0:
			leaf_x //= 2
			self.tree[leaf_x] = self.operator(self.tree[leaf_x * 2], self.tree[leaf_x * 2 + 1])

	def query(self, left, right):
		left += self.num_end_leaves
		left -= 1
		right += self.num_end_leaves
		val_l = val_r = self.identity
		while right - left > 0:
			if left & 1:
				val_l = self.operator(val_l, self.tree[left])
				left += 1
			if right & 1:
				right -= 1
				val_r = self.operator(self.tree[right], val_r)
			left >>= 1
			right >>= 1
		return self.operator(val_l, val_r)
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
st = segmentTree(a, max, 0)
res = list()
for _ in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		st.update(x - 1, y)
	elif t == 2:
		print(st.query(x, y))
	else:
		hi = n + 1
		lo = x - 1
		while hi - lo > 1:
			mid = (hi + lo) // 2
			if st.query(x, mid) >= y:
				hi = mid
			else:
				lo = mid
		print(lo + 1)


class SegmentTree:

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

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

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

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

	def get(self, p):
		return self.d[p + self.size]

	def prod(self, l, r):
		sml = smr = self.e
		l += self.size
		r += self.size
		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, f):
		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, f):
		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
import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())
A = tuple(map(int, input().split()))
st = SegmentTree(N, max, 0)
st.build(A)
res = []
for _ in range(Q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		st.set(x - 1, y)
	elif t == 2:
		res.append(st.prod(x - 1, y))
	else:
		res.append(st.max_right(x - 1, lambda z: z < y) + 1)
print('\n'.join(map(str, res)))


from math import ceil, log

class SegmentTree(object):
	__slots__ = ['elem_size', 'tree', 'default', 'op']

	def __init__(self, a: list, default: int, op):
		real_size = len(a)
		self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
		self.tree = tree = [default] * (elem_size * 2)
		tree[elem_size:elem_size + real_size] = a
		self.default = default
		self.op = op
		for i in range(elem_size - 1, 0, -1):
			tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

	def get(self, x: int, y: int) -> int:
		(l, r) = (x + self.elem_size, y + self.elem_size)
		(tree, result, op) = (self.tree, self.default, self.op)
		while l < r:
			if l & 1:
				result = op(tree[l], result)
				l += 1
			if r & 1:
				r -= 1
				result = op(tree[r], result)
			(l, r) = (l >> 1, r >> 1)
		return result

	def set(self, i: int, value: int) -> None:
		k = self.elem_size + i
		self.tree[k] = value
		self.__update(k)

	def __update(self, i: int) -> None:
		(op, tree) = (self.op, self.tree)
		while i > 1:
			i >>= 1
			tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

	def bisect_left(self, x: int, y: int, op):
		l = x
		r = y + 1
		while l + 1 != r:
			mid = (l + r) // 2
			if op(seg.get(l, mid)):
				r = mid
			else:
				l = mid
		return r
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
seg = SegmentTree(A, 0, max)
for i in range(Q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		seg.set(a - 1, b)
	elif t == 2:
		print(seg.get(a - 1, b))
	else:
		print(seg.bisect_left(a - 1, N, lambda x: x >= b))


class SegmentTree:
	__slots__ = ['func', 'e', 'original_size', 'n', 'data']

	def __init__(self, length_or_list, func, e):
		self.func = func
		self.e = e
		if isinstance(length_or_list, int):
			self.original_size = length_or_list
			self.n = 1 << (length_or_list - 1).bit_length()
			self.data = [self.e] * self.n
		else:
			self.original_size = len(length_or_list)
			self.n = 1 << (self.original_size - 1).bit_length()
			self.data = [self.e] * self.n + length_or_list + [self.e] * (self.n - self.original_size)
			for i in range(self.n - 1, 0, -1):
				self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def replace(self, index, value):
		index += self.n
		self.data[index] = value
		index //= 2
		while index > 0:
			self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
			index //= 2

	def folded(self, l, r):
		left_folded = self.e
		right_folded = self.e
		l += self.n
		r += self.n
		while l < r:
			if l % 2:
				left_folded = self.func(left_folded, self.data[l])
				l += 1
			if r % 2:
				r -= 1
				right_folded = self.func(self.data[r], right_folded)
			l //= 2
			r //= 2
		return self.func(left_folded, right_folded)

	def all_folded(self):
		return self.data[1]

	def get(self, index):
		return self.data[self.n + index]

	def max_right(self, l, f):
		if l >= self.original_size:
			return self.original_size
		l += self.n
		left_folded = self.e
		while True:
			while l % 2 == 0:
				l //= 2
			if not f(self.func(left_folded, self.data[l])):
				while l < self.n:
					l *= 2
					if f(self.func(left_folded, self.data[l])):
						left_folded = self.func(left_folded, self.data[l])
						l += 1
				return l - self.n
			left_folded = self.func(left_folded, self.data[l])
			l += 1
			if l == l & -l:
				break
		return self.original_size

	def min_left(self, r, f):
		if r <= 0:
			return 0
		r += self.n
		right_folded = self.e
		while True:
			r -= 1
			while r > 1 and r % 2:
				r //= 2
			if not f(self.func(self.data[r], right_folded)):
				while r < self.n:
					r = 2 * r + 1
					if f(self.func(self.data[r], right_folded)):
						right_folded = self.func(self.data[r], right_folded)
						r -= 1
				return r + 1 - self.n
			right_folded = self.func(self.data[r], right_folded)
			if r == r & -r:
				break
		return 0
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
As = list(map(int, input().split()))
seg = SegmentTree(As, max, 0)
for _ in range(Q):
	(T, X, V) = map(int, input().split())
	if T == 1:
		seg.replace(X - 1, V)
	elif T == 2:
		print(seg.folded(X - 1, V))
	else:
		print(seg.max_right(X - 1, lambda a: a < V) + 1)


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

class SegmentTree:

	def __init__(self, init, unitX, f):
		self.f = f
		self.unitX = unitX
		self.f = f
		if type(init) == int:
			self.n = init
			self.n = 1 << (self.n - 1).bit_length()
			self.X = [unitX] * (self.n * 2)
		else:
			self.n = len(init)
			self.n = 1 << (self.n - 1).bit_length()
			self.X = [unitX] * self.n + init + [unitX] * (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])

	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 getvalue(self, i):
		return self.X[i + self.n]

	def getrange(self, l, r):
		l += self.n
		r += self.n
		al = self.unitX
		ar = self.unitX
		while l < r:
			if l & 1:
				al = self.f(al, self.X[l])
				l += 1
			if r & 1:
				r -= 1
				ar = self.f(self.X[r], ar)
			l >>= 1
			r >>= 1
		return self.f(al, ar)

	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.X[l])):
				while l < self.n:
					l *= 2
					if z(self.f(s, self.X[l])):
						s = self.f(s, self.X[l])
						l += 1
				return l - self.n
			s = self.f(s, self.X[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.X[l], s)):
				while r < self.n:
					r = r * 2 + 1
					if z(self.f(self.X[l], s)):
						s = self.f(self.X[l], s)
						r -= 1
				return r + 1 - self.n
			s = self.f(self.X[r], s)
			if r & -r == r:
				break
		return 0
(N, Q) = map(int, input().split())
A = [int(a) for a in input().split()]
st = SegmentTree(A, 0, max)
for _ in range(Q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		st.update(a - 1, b)
	elif t == 2:
		print(st.getrange(a - 1, b))
	else:
		z = lambda x: x < b
		print(min(N, st.max_right(a - 1, z)) + 1)


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

def solve():

	def init(init_val):
		for i in range(n):
			seg[i + num - 1] = init_val[i]
		for i in range(num - 2, -1, -1):
			seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

	def update(k, x):
		k += num - 1
		seg[k] = x
		while k:
			k = (k - 1) // 2
			seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

	def query(p, q):
		if q <= p:
			return ide_ele
		p += num - 1
		q += num - 2
		res = ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = segfunc(res, seg[p])
			if q & 1 == 1:
				res = segfunc(res, seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = segfunc(res, seg[p])
		else:
			res = segfunc(segfunc(res, seg[p]), seg[q])
		return res
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	segfunc = lambda x, y: max(x, y)
	ide_ele = 0
	num = 2 ** (n - 1).bit_length()
	seg = [ide_ele] * 2 * num
	init(a)
	res = []
	for _ in range(q):
		(t, a, b) = map(int, input().split())
		if t == 1:
			update(a - 1, b)
		elif t == 2:
			res.append(query(a - 1, b))
		elif t == 3:
			ng = a - 1
			ok = n + 1
			while ok > ng + 1:
				mid = (ok + ng) // 2
				if query(ng, mid) >= b:
					ok = mid
				else:
					ng = mid
			res.append(ok)
	print('\n'.join(map(str, res)))
solve()


from copy import *
import sys
S = sys.stdin.readlines()

def init(N, node, unit, func):
	n = 1
	while n < N:
		n <<= 1
	for i in range(n * 2 - 1):
		if len(node) <= i:
			node.append(deepcopy(unit))
		else:
			node[i] = deepcopy(unit)
	node.append(func)
	node.append(unit)
	node.append(n)

def upd(node, x, a):
	y = node[-1] + x
	node[y - 1] = a
	while y > 1:
		y = y >> 1
		node[y - 1] = node[-3](node[(y << 1) - 1], node[y << 1])

def query(node, l, r):
	(x, y) = (l, r)
	z = node[-1] - 1
	r = node[-2]
	while True:
		if x == y:
			return r
		if x & 1:
			r = node[-3](r, node[x + z])
			x += 1
		if y & 1:
			r = node[-3](r, node[y + z - 1])
		x >>= 1
		y >>= 1
		z >>= 1
		if z == 0:
			return r

def bis_min_k(node, k, cond):
	x = k + 1
	while True:
		if node[-1] <= x:
			return x - node[-1]
		if cond(node[(x << 1) - 1]):
			x = x << 1
		else:
			x = (x << 1) + 1

def bis_min(node, l, r, cond):
	(x, y) = (l, r)
	z = node[-1] - 1
	for i in range(30):
		if x + (1 << i) > y:
			break
		if x & 1 << i:
			if cond(node[z + (x >> i)]):
				return bis_min_k(node, z + (x >> i), cond)
			x += 1 << i
		if z == 0:
			break
		z >>= 1
	for i in range(29, -1, -1):
		if i and node[-1] - 1 >> i - 1 == 0:
			continue
		if x + (1 << i) > y:
			continue
		if y - x & 1 << i:
			if cond(node[(node[-1] - 1 >> i) + (x >> i)]):
				return bis_min_k(node, (node[-1] - 1 >> i) + (x >> i), cond)
			x += 1 << i
	return node[-1]
(N, Q) = map(int, S[0].split())
A = list(map(int, S[1].split()))
X = []
init(N + 1, X, -1, lambda x, y: max(x, y))
for i in range(N):
	upd(X, i, A[i])
(t, a, b) = (0, 0, 0)
for i in range(Q):
	(t, a, b) = map(int, S[i + 2].split())
	if t == 1:
		upd(X, a - 1, b)
	elif t == 2:
		print(query(X, a - 1, b))
	else:
		a = bis_min(X, a - 1, N, lambda x: b <= x)
		if a > N:
			print(N + 1)
		else:
			print(a + 1)


import sys
input = sys.stdin.readline

class segtree:
	x_unit = 0
	x_func = max

	def __init__(self, n):
		self.n = n
		self.x = [self.x_unit] * (2 * n)

	def build(self, seq):
		for (i, j) in enumerate(seq, self.n):
			self.x[i] = j
		for i in range(self.n - 1, 0, -1):
			self.x[i] = self.x_func(self.x[i * 2], self.x[i * 2 + 1])

	def update(self, i, j):
		i += self.n
		self.x[i] = j
		while i > 1:
			i //= 2
			self.x[i] = self.x_func(self.x[i * 2], self.x[i * 2 + 1])

	def fold(self, l, r):
		l += self.n
		r += self.n
		val_l = self.x_unit
		val_r = self.x_unit
		while l < r:
			if l & 1:
				val_l = self.x_func(val_l, self.x[l])
				l += 1
			if r & 1:
				r -= 1
				val_r = self.x_func(val_r, self.x[r])
			l //= 2
			r //= 2
		return self.x_func(val_l, val_r)

	def find_j(self, l, v):
		r = self.n
		if self.fold(l, r) < v:
			return r
		else:
			while r - l > 1:
				l1 = l
				r1 = l + (r - l) // 2
				l2 = l + (r - l) // 2
				r2 = r
				if self.fold(l1, r1) >= v:
					l = l1
					r = r1
				else:
					l = l2
					r = r2
			return l
(n, q) = map(int, input().split())
seg = segtree(n)
(*a,) = map(int, input().split())
seg.build(a)
for i in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		x -= 1
		seg.update(x, y)
	elif t == 2:
		print(seg.fold(x - 1, y))
	else:
		print(seg.find_j(x - 1, y) + 1)


import types
_atcoder_code = "\n# Python port of AtCoder Library.\n\n__version__ = '0.0.1'\n"
atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)
_atcoder__bit_code = '\ndef _ceil_pow2(n: int) -> int:\n    x = 0\n    while (1 << x) < n:\n        x += 1\n\n    return x\n\n\ndef _bsf(n: int) -> int:\n    x = 0\n    while n % 2 == 0:\n        x += 1\n        n //= 2\n\n    return x\n'
atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)
_atcoder_segtree_code = '\nimport typing\n\n# import atcoder._bit\n\n\nclass SegTree:\n    def __init__(self,\n                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],\n                 e: typing.Any,\n                 v: typing.Union[int, typing.List[typing.Any]]) -> None:\n        self._op = op\n        self._e = e\n\n        if isinstance(v, int):\n            v = [e] * v\n\n        self._n = len(v)\n        self._log = atcoder._bit._ceil_pow2(self._n)\n        self._size = 1 << self._log\n        self._d = [e] * (2 * self._size)\n\n        for i in range(self._n):\n            self._d[self._size + i] = v[i]\n        for i in range(self._size - 1, 0, -1):\n            self._update(i)\n\n    def set(self, p: int, x: typing.Any) -> None:\n        assert 0 <= p < self._n\n\n        p += self._size\n        self._d[p] = x\n        for i in range(1, self._log + 1):\n            self._update(p >> i)\n\n    def get(self, p: int) -> typing.Any:\n        assert 0 <= p < self._n\n\n        return self._d[p + self._size]\n\n    def prod(self, left: int, right: int) -> typing.Any:\n        assert 0 <= left <= right <= self._n\n        sml = self._e\n        smr = self._e\n        left += self._size\n        right += self._size\n\n        while left < right:\n            if left & 1:\n                sml = self._op(sml, self._d[left])\n                left += 1\n            if right & 1:\n                right -= 1\n                smr = self._op(self._d[right], smr)\n            left >>= 1\n            right >>= 1\n\n        return self._op(sml, smr)\n\n    def all_prod(self) -> typing.Any:\n        return self._d[1]\n\n    def max_right(self, left: int,\n                  f: typing.Callable[[typing.Any], bool]) -> int:\n        assert 0 <= left <= self._n\n        assert f(self._e)\n\n        if left == self._n:\n            return self._n\n\n        left += self._size\n        sm = self._e\n\n        first = True\n        while first or (left & -left) != left:\n            first = False\n            while left % 2 == 0:\n                left >>= 1\n            if not f(self._op(sm, self._d[left])):\n                while left < self._size:\n                    left *= 2\n                    if f(self._op(sm, self._d[left])):\n                        sm = self._op(sm, self._d[left])\n                        left += 1\n                return left - self._size\n            sm = self._op(sm, self._d[left])\n            left += 1\n\n        return self._n\n\n    def min_left(self, right: int,\n                 f: typing.Callable[[typing.Any], bool]) -> int:\n        assert 0 <= right <= self._n\n        assert f(self._e)\n\n        if right == 0:\n            return 0\n\n        right += self._size\n        sm = self._e\n\n        first = True\n        while first or (right & -right) != right:\n            first = False\n            right -= 1\n            while right > 1 and right % 2:\n                right >>= 1\n            if not f(self._op(self._d[right], sm)):\n                while right < self._size:\n                    right = 2 * right + 1\n                    if f(self._op(self._d[right], sm)):\n                        sm = self._op(self._d[right], sm)\n                        right -= 1\n                return right + 1 - self._size\n            sm = self._op(self._d[right], sm)\n\n        return 0\n\n    def _update(self, k: int) -> None:\n        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])\n'
atcoder.segtree = types.ModuleType('atcoder.segtree')
exec(_atcoder_segtree_code, atcoder.segtree.__dict__)
atcoder.segtree.__dict__['atcoder'] = atcoder
atcoder.segtree.__dict__['atcoder._bit'] = atcoder._bit
SegTree = atcoder.segtree.SegTree
import sys

def main() -> None:
	(n, q) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	segtree = SegTree(max, -1, a)
	for _ in range(q):
		(t, x, y) = map(int, sys.stdin.readline().split())
		if t == 1:
			segtree.set(x - 1, y)
		elif t == 2:
			print(segtree.prod(x - 1, y))
		else:
			print(segtree.max_right(x - 1, lambda v: v < y) + 1)
main()


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.n = 1 << (self.n - 1).bit_length()
			self.X = [unitX] * (self.n * 2)
			self.size = [1] * (self.n * 2)
		else:
			self.n = len(init)
			self.n = 1 << (self.n - 1).bit_length()
			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
f = lambda x, y: max(x, y)
g = lambda x, a, s: max(x, a)
h = lambda a, b: max(a, b)
unitX = 0
unitA = 0
(N, Q) = map(int, input().split())
A = [int(a) for a in input().split()]
st = LazySegmentTree(A, unitX, unitA, f, g, h)
for _ in range(Q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		st.update(a - 1, b)
	elif t == 2:
		print(st.getrange(a - 1, b))
	else:
		z = lambda x: x < b
		print(min(N, st.max_right(a - 1, z)) + 1)


class segtree:

	def __init__(s, v, op, e):
		s._n = len(v)
		s.log = s.ceil_pow2(s._n)
		s.size = 1 << s.log
		s.d = [e()] * (2 * s.size)
		s.e = e
		s.op = op
		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
		s.d[p] = x
		for i in range(1, s.log + 1):
			s.update(p >> i)

	def get(s, p):
		return s.d[p + s.size]

	def prod(s, l, r):
		(sml, smr) = (s.e(), s.e())
		l += s.size
		r += s.size
		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 max_right(s, l, g):
		if l == s._n:
			return s._n
		l += s.size
		sm = s.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(s.op(sm, s.d[l])):
				while l < s.size:
					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
		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:
					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 ceil_pow2(s, n):
		x = 0
		while 1 << x < n:
			x += 1
		return x
import sys

def e():
	return 0

def op(s, t):
	return max(s, t)
(N, Q) = list(map(int, input().split()))
A = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
seg = segtree(A, op, e)
for q in Query:
	if q[0] == 1:
		(_, x, v) = q
		seg.set(x - 1, v)
	elif q[0] == 2:
		(_, l, r) = q
		print(seg.prod(l - 1, r))
	elif q[0] == 3:
		(_, x, v) = q

		def g(n):
			return n < v
		print(seg.max_right(x - 1, g) + 1)


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 SegmentTree:

	def __init__(self, array, function, identify):
		self.length = len(array)
		(self.func, self.ide_ele) = (function, identify)
		self.size = 1 << (self.length - 1).bit_length()
		self.data = [self.ide_ele] * 2 * self.size
		for i in range(self.length):
			self.data[self.size + i] = array[i]
		for i in range(self.size - 1, 0, -1):
			self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def update(self, idx, x):
		idx += self.size
		self.data[idx] = x
		while idx > 0:
			idx >>= 1
			self.data[idx] = self.func(self.data[2 * idx], self.data[2 * idx + 1])

	def query(self, l, r):
		l += self.size
		r += self.size + 1
		l_ret = r_ret = self.ide_ele
		while l < r:
			if l & 1:
				l_ret = self.func(l_ret, self.data[l])
				l += 1
			if r & 1:
				r -= 1
				r_ret = self.func(self.data[r], r_ret)
			l >>= 1
			r >>= 1
		return self.func(l_ret, r_ret)

	def get(self, idx):
		return self.data[idx + self.size]

def Main():
	(n, q) = read_ints()
	a = read_int_list()
	seg = SegmentTree(a, max, -float('inf'))
	for _ in range(q):
		(t, x, v) = read_ints()
		if t == 1:
			seg.update(~-x, v)
		elif t == 2:
			print(seg.query(~-x, ~-v))
		else:
			l = x - 1
			r = n + 1
			while r - l > 1:
				mid = (l + r) // 2
				if seg.query(~-x, ~-mid) >= v:
					r = mid
				else:
					l = mid
			print(r)
Main()


class SegmentTree:

	def __init__(self, n, func, init=float('inf')):
		self.n = 2 ** (n - 1).bit_length()
		self.init = init
		self.data = [init] * (2 * self.n)
		self.func = func

	def set(self, i, v):
		self.data[i + self.n - 1] = v

	def build(self):
		for k in reversed(range(self.n - 1)):
			self.data[k] = self.func(self.data[k * 2 + 1], self.data[k * 2 + 2])

	def update(self, k, a):
		k += self.n - 1
		self.data[k] = a
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.func(self.data[k * 2 + 1], self.data[k * 2 + 2])

	def query(self, l, r):
		L = l + self.n
		R = r + self.n
		ret = self.init
		while L < R:
			if R & 1:
				R -= 1
				ret = self.func(ret, self.data[R - 1])
			if L & 1:
				ret = self.func(ret, self.data[L - 1])
				L += 1
			L >>= 1
			R >>= 1
		return ret

	def lower_bound_index(self, x, v):
		x += self.n - 1
		while self.data[x] < v:
			if x % 2 == 0:
				if len(bin(x + 1)) == len(bin(x + 2)):
					x += 1
				else:
					return float('inf')
			else:
				x >>= 1
		while x < self.n - 1:
			if self.data[2 * x + 1] >= v:
				x = 2 * x + 1
			else:
				x = 2 * x + 2
		return x - self.n + 1
(N, Q) = map(int, input().split())
Seg = SegmentTree(N, lambda x, y: max(x, y), init=-1)
A = list(map(int, input().split()))
for (i, a) in enumerate(A):
	Seg.set(i, a)
Seg.build()
for _ in range(Q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		Seg.update(a - 1, b)
	elif t == 2:
		print(Seg.query(a - 1, b))
	elif t == 3:
		print(min(Seg.lower_bound_index(a - 1, b), N) + 1)


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

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

	class SegmentTree:

		def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
			self.N = len(A)
			self.LV = (self.N - 1).bit_length()
			self.N0 = 1 << self.LV
			self.segfunc = segfunc
			self.ident = ident
			if initialize:
				self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
				for i in range(self.N0 - 1, 0, -1):
					self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
			else:
				self.data = [self.ident] * (self.N0 * 2)

		def update(self, i, x):
			i += self.N0 - 1
			self.data[i] = x
			for _ in range(self.LV):
				i >>= 1
				self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

		def query(self, l, r):
			l += self.N0 - 1
			r += self.N0 - 1
			ret_l = self.ident
			ret_r = self.ident
			while l < r:
				if l & 1:
					ret_l = self.segfunc(ret_l, self.data[l])
					l += 1
				if r & 1:
					ret_r = self.segfunc(self.data[r - 1], ret_r)
					r -= 1
				l >>= 1
				r >>= 1
			return self.segfunc(ret_l, ret_r)

		def binsearch(self, l, r, check):
			if not check(self.query(l, r)):
				return r
			l += self.N0 - 1
			val = self.ident
			while True:
				if check(self.segfunc(val, self.data[l])):
					break
				if l & 1:
					val = self.segfunc(val, self.data[l])
					l += 1
				l >>= 1
			while l < self.N0:
				newval = self.segfunc(val, self.data[l * 2])
				if not check(newval):
					val = newval
					l = (l << 1) + 1
				else:
					l <<= 1
			return l - self.N0 + 1

	def check(val):
		return val >= v
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	ST = SegmentTree(A, segfunc=max, ident=-2000000000)
	for _ in range(Q):
		(t, x, v) = map(int, input().split())
		if t == 1:
			ST.update(x, v)
		elif t == 2:
			l = x
			r = v + 1
			print(ST.query(l, r))
		else:
			print(ST.binsearch(x, N + 1, check))
main()


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())
A = tuple(map(int, input().split()))
eq = lambda x, y: y
lst = LazySegmentTree(N, max, 0, eq, eq, 0)
lst.build(A)
res = []
for _ in range(Q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		lst.set(x - 1, y)
	elif t == 2:
		res.append(lst.prod(x - 1, y))
	else:
		res.append(lst.max_right(x - 1, lambda z: z < y) + 1)
print('\n'.join(map(str, res)))


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

class Segtree:

	def __init__(self, A, intv, initialize=True, segf=max):
		self.N = len(A)
		self.N0 = 2 ** (self.N - 1).bit_length()
		self.intv = intv
		self.segf = segf
		if initialize:
			self.data = [intv] * self.N0 + A + [intv] * (self.N0 - self.N)
			for i in range(self.N0 - 1, 0, -1):
				self.data[i] = self.segf(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [intv] * (2 * self.N0)

	def update(self, k, x):
		k += self.N0
		self.data[k] = x
		while k > 0:
			k = k >> 1
			self.data[k] = self.segf(self.data[2 * k], self.data[2 * k + 1])

	def query(self, l, r):
		(L, R) = (l + self.N0, r + self.N0)
		s = self.intv
		while L < R:
			if R & 1:
				R -= 1
				s = self.segf(s, self.data[R])
			if L & 1:
				s = self.segf(s, self.data[L])
				L += 1
			L >>= 1
			R >>= 1
		return s

	def binsearch(self, l, r, check, reverse=False):
		(L, R) = (l + self.N0, r + self.N0)
		(SL, SR) = ([], [])
		while L < R:
			if R & 1:
				R -= 1
				SR.append(R)
			if L & 1:
				SL.append(L)
				L += 1
			L >>= 1
			R >>= 1
		if reverse:
			pre = self.intv
			for idx in SR + SL[::-1]:
				if check(self.segf(self.data[idx], pre)):
					break
				else:
					pre = self.segf(self.data[idx], pre)
			else:
				return -1
			while idx < self.N0:
				if check(self.segf(self.data[2 * idx + 1], pre)):
					idx = 2 * idx + 1
				else:
					pre = self.segf(self.data[2 * idx + 1], pre)
					idx = 2 * idx
			return idx - self.N0
		else:
			pre = self.intv
			for idx in SL + SR[::-1]:
				if not check(self.segf(pre, self.data[idx])):
					pre = self.segf(pre, self.data[idx])
				else:
					break
			else:
				return -1
			while idx < self.N0:
				if check(self.segf(pre, self.data[2 * idx])):
					idx = 2 * idx
				else:
					pre = self.segf(pre, self.data[2 * idx])
					idx = 2 * idx + 1
			return idx - self.N0
(N, Q) = map(int, readline().split())
A = list(map(int, readline().split()))
INF = 10 ** 9 + 7
T = Segtree(A, -INF, initialize=True, segf=max)
Ans = []
N0 = T.N0
for _ in range(Q):
	(t, x, v) = map(int, readline().split())
	if t == 1:
		T.update(x - 1, v)
	elif t == 2:
		Ans.append(T.query(x - 1, v))
	else:
		k = T.binsearch(x - 1, N0, lambda x: x >= v)
		if k == -1:
			Ans.append(N + 1)
		else:
			Ans.append(k + 1)
print('\n'.join(map(str, Ans)))


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

class SegmentTree:
	__slots__ = ['e', 'op', '_n', '_size', 'tree']

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

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

	def set(self, k: int, x: S) -> None:
		assert 0 <= k < self._n
		k += self._size
		self.tree[k] = x
		while k:
			k >>= 1
			self._update(k)

	def get(self, k: int) -> S:
		assert 0 <= k < self._n
		return self.tree[k + self._size]

	def prod(self, l: int, r: int) -> S:
		assert 0 <= l <= r <= self._n
		(sml, smr) = (self.e, self.e)
		l += self._size
		r += self._size
		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 max_right(self, l: int, f: Callable[[S], bool]) -> int:
		assert 0 <= l <= self._n
		assert f(self.e)
		if l == self._n:
			return self._n
		l += self._size
		sm = self.e
		while True:
			while not l & 1:
				l >>= 1
			if not f(self.op(sm, self.tree[l])):
				while l < self._size:
					l *= 2
					if f(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, f: Callable[[S], bool]) -> int:
		assert 0 <= r <= self._n
		assert f(self.e)
		if not r:
			return 0
		r += self._size
		sm = self.e
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not f(self.op(self.tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if f(self.op(self.tree[r], sm)):
						sm = self.op(self.tree[r], sm)
						r -= 1
				return r + 1 - self._size
			if r & -r == r:
				break
		return 0
import sys
readline = sys.stdin.buffer.readline
(N, Q) = map(int, readline().split())
(*A,) = map(int, readline().split())
tree = SegmentTree(A, -1, max)
res = []
for _ in range(Q):
	(t, x, y) = map(int, readline().split())
	if t == 1:
		tree.set(x - 1, y)
	elif t == 2:
		res.append(tree.prod(x - 1, y))
	else:
		res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
print('\n'.join(map(str, res)))


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 SegmentTree:

	def __init__(self, size, f=lambda x, y: x + y, default=0):
		self.size = 2 ** (size - 1).bit_length()
		self.default = default
		self.data = [default] * (self.size * 2)
		self.f = f

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

	def query(self, l, r):
		l += self.size
		r += self.size
		(lres, rres) = (self.default, self.default)
		while l < r:
			if l & 1:
				lres = self.f(lres, self.data[l])
				l += 1
			if r & 1:
				r -= 1
				rres = self.f(self.data[r], rres)
			l >>= 1
			r >>= 1
		res = self.f(lres, rres)
		return res

	def lower_bound(self, x, v):
		x += self.size
		while self.data[x] < v:
			if x & 1:
				if len(bin(x)) == len(bin(x + 1)):
					x += 1
				else:
					return self.size
			else:
				x >>= 1
		while x < self.size:
			if self.data[2 * x] >= v:
				x = 2 * x
			else:
				x = 2 * x + 1
		return x - self.size

def main():
	(N, Q) = LI()
	A = LI()
	query = LIR(Q)
	tree = SegmentTree(N, f=max, default=-1)
	for (i, ai) in enumerate(A):
		tree.update(i, ai)
	for (t, a, b) in query:
		if t == 1:
			tree.update(a - 1, b)
		elif t == 2:
			print(tree.query(a - 1, b))
		else:
			print(min(tree.lower_bound(a - 1, b), N) + 1)
main()


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

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

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

def main():

	class Segtree:

		def __init__(self, A, ide_ele, initialize=True, segf=max):
			self.N = len(A)
			self.N0 = 2 ** (self.N - 1).bit_length()
			self.ide_ele = ide_ele
			self.segf = segf
			if initialize:
				self.data = [ide_ele] * self.N0 + A + [ide_ele] * (self.N0 - self.N)
				for i in range(self.N0 - 1, 0, -1):
					self.data[i] = self.segf(self.data[2 * i], self.data[2 * i + 1])
			else:
				self.data = [ide_ele] * (2 * self.N0)

		def update(self, k, x):
			k += self.N0
			self.data[k] = x
			while k > 0:
				k = k >> 1
				self.data[k] = self.segf(self.data[2 * k], self.data[2 * k + 1])

		def query(self, l, r):
			(L, R) = (l + self.N0, r + self.N0)
			s = self.ide_ele
			while L < R:
				if R & 1:
					R -= 1
					s = self.segf(s, self.data[R])
				if L & 1:
					s = self.segf(s, self.data[L])
					L += 1
				L >>= 1
				R >>= 1
			return s

		def binsearch(self, l, r, check, reverse=False):
			(L, R) = (l + self.N0, r + self.N0)
			(SL, SR) = ([], [])
			while L < R:
				if R & 1:
					R -= 1
					SR.append(R)
				if L & 1:
					SL.append(L)
					L += 1
				L >>= 1
				R >>= 1
			if reverse:
				pre = self.ide_ele
				for idx in SR + SL[::-1]:
					if check(self.segf(self.data[idx], pre)):
						break
					else:
						pre = self.segf(self.data[idx], pre)
				else:
					return None
				while idx < self.N0:
					if check(self.segf(self.data[2 * idx + 1], pre)):
						idx = 2 * idx + 1
					else:
						pre = self.segf(self.data[2 * idx + 1], pre)
						idx = 2 * idx
				return idx - self.N0
			else:
				pre = self.ide_ele
				for idx in SL + SR[::-1]:
					if not check(self.segf(pre, self.data[idx])):
						pre = self.segf(pre, self.data[idx])
					else:
						break
				else:
					return None
				while idx < self.N0:
					if check(self.segf(pre, self.data[2 * idx])):
						idx = 2 * idx
					else:
						pre = self.segf(pre, self.data[2 * idx])
						idx = 2 * idx + 1
				return idx - self.N0
	(N, Q) = MI()
	A = LI()
	seg = Segtree(A, 0, segf=max)
	N0 = seg.N0
	for _ in range(Q):
		(t, x, v) = MI()
		if t == 1:
			x -= 1
			seg.update(x, v)
		elif t == 2:
			l = x - 1
			r = v
			print(seg.query(l, r))
		else:
			l = x - 1
			r = N
			ans = seg.binsearch(l, r, lambda x: x >= v)
			if ans == None:
				ans = N
			print(ans + 1)
main()


from typing import Callable, Iterator, Optional, TypeVar
S = TypeVar('S')

class SegmentTree:
	__slots__ = ['_e', '_op', '_n', '_size', '_tree']

	def __init__(self, values: Optional[Iterator[S]], n: int, e: S, op: Callable[[S, S], S]) -> None:
		self._e = e
		self._op = op
		self._n = n
		self._size = 1 << (self._n - 1).bit_length()
		self._tree = [e] * 2 * self._size
		if values is None:
			return
		for (i, values) in enumerate(values, self._size):
			self._tree[i] = values
		for i in range(self._size - 1, 0, -1):
			self._update(i)

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

	def set(self, k: int, x: S) -> None:
		assert 0 <= k < self._n
		k += self._size
		self._tree[k] = x
		while k:
			k >>= 1
			self._update(k)

	def get(self, k: int) -> S:
		assert 0 <= k < self._n
		return self._tree[k + self._size]

	def prod(self, l: int, r: int) -> S:
		assert 0 <= l <= r <= self._n
		(sml, smr) = (self._e, self._e)
		l += self._size
		r += self._size
		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 max_right(self, l: int, f: Callable[[S], bool]) -> int:
		assert 0 <= l <= self._n
		assert f(self._e)
		if l == self._n:
			return self._n
		l += self._size
		sm = self._e
		while True:
			while not l & 1:
				l >>= 1
			if not f(self._op(sm, self._tree[l])):
				while l < self._size:
					l *= 2
					if f(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, f: Callable[[S], bool]) -> int:
		assert 0 <= r <= self._n
		assert f(self._e)
		if not r:
			return 0
		r += self._size
		sm = self._e
		while True:
			r -= 1
			while r > 1 and r & 1:
				r >>= 1
			if not f(self._op(self._tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if f(self._op(self._tree[r], sm)):
						sm = self._op(self._tree[r], sm)
						r -= 1
				return r + 1 - self._size
			if r & -r == r:
				break
		return 0

def staticrmq():
	import sys
	read = sys.stdin.buffer.read
	readline = sys.stdin.buffer.readline
	(N, _) = map(int, readline().split())
	A = map(int, readline().split())
	LR = map(int, read().split())
	tree = SegmentTree(A, N, 10 ** 10 + 1, min)
	res = [tree.prod(l, r) for (l, r) in zip(*[iter(LR)] * 2)]
	print('\n'.join(map(str, res)))

def practice2_j():
	import sys
	readline = sys.stdin.readline
	(N, Q) = map(int, readline().split())
	A = map(int, readline().split())
	tree = SegmentTree(A, N, -1, max)
	res = []
	for _ in range(Q):
		(t, x, y) = map(int, readline().split())
		if t == 1:
			tree.set(x - 1, y)
		elif t == 2:
			res.append(tree.prod(x - 1, y))
		else:
			res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
	print('\n'.join(map(str, res)))

def dsl_2_a():
	(N, Q, *X) = map(int, open(0).read().split())
	tree = SegmentTree(None, N, 2 ** 31 - 1, min)
	res = []
	for (com, x, y) in zip(*[iter(X)] * 3):
		if com:
			res.append(tree.prod(x, y + 1))
		else:
			tree.set(x, y)
	print('\n'.join(map(str, res)))

def abc125_c():
	from math import gcd
	(N, *A) = map(int, open(0).read().split())
	tree = SegmentTree(A, N, 0, gcd)
	res = max((gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N)))
	print(res)
practice2_j()


class LazyPropSegmentTree:

	def __init__(self, n, f, g, h, ef, eh):
		self.n = n
		self.f = f
		self.g = lambda xh, x, l: g(xh, x, l) if xh != eh else x
		self.h = h
		self.ef = ef
		self.eh = eh
		l = (self.n - 1).bit_length()
		self.size = 1 << l
		self.tree = [self.ef] * (self.size << 1)
		self.lazy = [self.eh] * ((self.size << 1) + 1)
		self.plt_cnt = 0
		self.length = [0]
		for i in range(l + 1):
			self.length += [1 << l - i] * (1 << i)

	def built(self, array):
		(size, tree, f) = (self.size, self.tree, self.f)
		for i in range(self.n):
			tree[size + i] = array[i]
		for i in range(size - 1, 0, -1):
			tree[i] = f(tree[i << 1], tree[i << 1 | 1])

	def update(self, i, x):
		(size, tree, lazy, eh) = (self.size, self.tree, self.lazy, self.eh)
		i += size
		self.propagate_lazy(i)
		tree[i] = x
		lazy[i] = eh
		self.propagate_tree(i)

	def get(self, i):
		(size, tree, lazy, length, g) = (self.size, self.tree, self.lazy, self.length, self.g)
		i += size
		self.propagate_lazy(i)
		return g(lazy[i], tree[i], length[i])

	def update_range(self, l, r, x):
		(size, lazy, h) = (self.size, self.lazy, self.h)
		if l >= r:
			return
		l += size
		r += size
		l0 = l // (l & -l)
		r0 = r // (r & -r)
		self.propagate_lazy(l0)
		self.propagate_lazy(r0 - 1)
		while l < r:
			if r & 1:
				r -= 1
				lazy[r] = h(x, lazy[r])
			if l & 1:
				lazy[l] = h(x, lazy[l])
				l += 1
			l >>= 1
			r >>= 1
		self.propagate_tree(l0)
		self.propagate_tree(r0 - 1)

	def get_range(self, l, r):
		(size, tree, lazy, length, ef, f, g) = (self.size, self.tree, self.lazy, self.length, self.ef, self.f, self.g)
		l += size
		r += size
		self.propagate_lazy(l // (l & -l))
		self.propagate_lazy(r // (r & -r) - 1)
		res_l = ef
		res_r = ef
		while l < r:
			if l & 1:
				res_l = f(res_l, g(lazy[l], tree[l], length[l]))
				l += 1
			if r & 1:
				r -= 1
				res_r = f(g(lazy[r], tree[r], length[r]), res_r)
			l >>= 1
			r >>= 1
		return f(res_l, res_r)

	def max_right(self, l, z):
		if l >= self.n:
			return self.n
		l += self.size
		s = self.ef
		while 1:
			while l % 2 == 0:
				l >>= 1
			if not z(self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))):
				while l < self.size:
					l *= 2
					if z(self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))):
						s = self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))
						l += 1
				return l - self.size
			s = self.f(s, self.g(self.lazy[l], self.tree[l], self.length[l]))
			l += 1
			if l & -l == l:
				break
		return self.n

	def min_left(self, r, z):
		if r <= 0:
			return 0
		r += self.size
		s = self.ef
		while 1:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
				while r < self.size:
					r = r * 2 + 1
					if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
						s = self.f(self.g(self.lazy[r], self.tree[r]), s)
						r -= 1
				return r + 1 - self.size
			s = self.f(self.g(self.lazy[r], self.tree[r]), s)
			if r & -r == r:
				break
		return 0

	def propagate_lazy(self, i):
		(tree, lazy, length, eh, h, f, g) = (self.tree, self.lazy, self.length, self.eh, self.h, self.f, self.g)
		for k in range(i.bit_length() - 1, 0, -1):
			x = i >> k
			if lazy[x] == eh:
				continue
			laz = lazy[x]
			lazy[x << 1 | 1] = h(laz, lazy[x << 1 | 1])
			lazy[x << 1] = h(laz, lazy[x << 1])
			tree[x] = g(laz, tree[x], length[x])
			lazy[x] = eh

	def propagate_tree(self, i):
		(tree, lazy, length, f, g) = (self.tree, self.lazy, self.length, self.f, self.g)
		while i > 1:
			i >>= 1
			tree[i] = f(g(lazy[i << 1], tree[i << 1], length[i << 1]), g(lazy[i << 1 | 1], tree[i << 1 | 1], length[i << 1]))

	def __getitem__(self, i):
		return self.get(i)

	def __iter__(self):
		(size, tree, lazy, length, eh, h, g) = (self.size, self.tree, self.lazy, self.length, self.eh, self.h, self.g)
		for x in range(1, size):
			if lazy[x] == eh:
				continue
			lazy[x << 1 | 1] = h(lazy[x], lazy[x << 1 | 1])
			lazy[x << 1] = h(lazy[x], lazy[x << 1])
			self.tree[x] = self.g(self.lazy[x], self.tree[x])
			lazy[x] = eh
		for (xh, x) in zip(lazy[size:size + self.n], tree[size:size + self.n]):
			yield g(xh, x, 1)

	def __str__(self):
		return str(list(self))

	def debug(self):
		(tree, lazy) = (self.tree, self.lazy)

		def full_tree_pos(G):
			n = G.number_of_nodes()
			if n == 0:
				return {}
			pos = {0: (0.5, 0.9)}
			if n == 1:
				return pos
			i = 1
			while not n >= 2 ** i or not n < 2 ** (i + 1):
				i += 1
			height = i
			(p_key, p_y, p_x) = (0, 0.9, 0.5)
			l_child = True
			for i in range(height):
				for j in range(2 ** (i + 1)):
					if 2 ** (i + 1) + j - 1 < n:
						if l_child == True:
							pos[2 ** (i + 1) + j - 1] = (p_x - 0.2 / (i * i + 1), p_y - 0.1)
							G.add_edge(2 ** (i + 1) + j - 1, p_key)
							l_child = False
						else:
							pos[2 ** (i + 1) + j - 1] = (p_x + 0.2 / (i * i + 1), p_y - 0.1)
							l_child = True
							G.add_edge(2 ** (i + 1) + j - 1, p_key)
							p_key += 1
							(p_x, p_y) = pos[p_key]
			return pos
		import networkx as nx
		import matplotlib.pyplot as plt
		A = tree[1:]
		G = nx.Graph()
		labels = {}
		for (i, a) in enumerate(A):
			G.add_node(i)
			labels[i] = a
		pos = full_tree_pos(G)
		nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
		plt.savefig('tree-{0}.png'.format(self.plt_cnt))
		plt.clf()
		A = lazy[1:-1]
		G = nx.Graph()
		labels = {}
		for (i, a) in enumerate(A):
			G.add_node(i)
			labels[i] = a
		pos = full_tree_pos(G)
		nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
		plt.savefig('lazy-{0}.png'.format(self.plt_cnt))
		plt.clf()
		self.plt_cnt += 1
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
ef = 0
eh = 0
f = lambda x, y: x if x > y else y
g = lambda x, y, s: x if x > y else y
h = lambda x, y: x if x > y else y
st = LazyPropSegmentTree(N, f, g, h, ef, eh)
st.built(A)
res = []
for _ in range(Q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		st.update(x - 1, y)
	elif t == 2:
		res.append(st.get_range(x - 1, y))
	else:
		res.append(st.max_right(x - 1, lambda z: z < y) + 1)
print('\n'.join(map(str, res)))


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
qs = [tuple(map(int, input().split())) for i in range(Q)]

class SegTree:

	def __init__(self, arr, func, unit):
		self.func = func
		self.unit = unit
		n = 1
		while n < len(arr):
			n *= 2
		self.n = n
		nodes = [unit] * (2 * n - 1)
		nodes[n - 1:n - 1 + len(arr)] = arr
		for i in range(n - 2, -1, -1):
			nodes[i] = func(nodes[2 * i + 1], nodes[2 * i + 2])
		self.nodes = nodes

	def update(self, i, val):
		i += self.n - 1
		self.nodes[i] = val
		while i >= 0:
			i = (i - 1) // 2
			self.nodes[i] = self.func(self.nodes[2 * i + 1], self.nodes[2 * i + 2])

	def query(self, l, r):
		l += self.n
		r += self.n
		s = self.unit
		while l < r:
			if r & 1:
				r -= 1
				s = self.func(self.nodes[r - 1], s)
			if l & 1:
				s = self.func(s, self.nodes[l - 1])
				l += 1
			l >>= 1
			r >>= 1
		return s
INF = float('inf')
segt = SegTree(A, lambda x, y: max(x, y), -INF)
ans = []
for (a, b, c) in qs:
	if a == 1:
		segt.update(b - 1, c)
	elif a == 2:
		ans.append(segt.query(b - 1, c))
	else:
		l = b - 1
		r = N
		if segt.query(l, r) < c:
			ans.append(N + 1)
		else:
			while r - l > 1:
				m = (l + r) // 2
				if segt.query(l, m) >= c:
					r = m
				else:
					l = m
			ans.append(r)
print(*ans, sep='\n')


class SegmentTree:

	def __init__(self, arr, func=min, ie=2 ** 63):
		self.h = (len(arr) - 1).bit_length()
		self.n = 2 ** self.h
		self.ie = ie
		self.func = func
		self.tree = [ie for _ in range(2 * self.n)]
		for i in range(len(arr)):
			self.tree[self.n + i] = arr[i]
		for i in range(1, self.n)[::-1]:
			self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

	def set(self, idx, x):
		idx += self.n
		self.tree[idx] = x
		while idx:
			idx >>= 1
			self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

	def query(self, lt, rt):
		lt += self.n
		rt += self.n
		vl = vr = self.ie
		while rt - lt > 0:
			if lt & 1:
				vl = self.func(vl, self.tree[lt])
				lt += 1
			if rt & 1:
				rt -= 1
				vr = self.func(self.tree[rt], vr)
			lt >>= 1
			rt >>= 1
		return self.func(vl, vr)
import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
st = SegmentTree(A, max, 0)
res = list()
for _ in range(Q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		st.set(x - 1, y)
	elif t == 2:
		res.append(st.query(x - 1, y))
	else:
		hi = N + 1
		lo = x - 1
		while hi - lo > 1:
			mid = (hi + lo) // 2
			if st.query(x - 1, mid) >= y:
				hi = mid
			else:
				lo = mid
		res.append(lo + 1)
print('\n'.join(map(str, res)))


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, left, right):
		res = self.ide_ele
		left += self.num
		right += self.num
		while left < right:
			if left & 1:
				res = self.segfunc(res, self.tree[left])
				left += 1
			if right & 1:
				res = self.segfunc(res, self.tree[right - 1])
			left >>= 1
			right >>= 1
		return res

def resolve():
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	seg = SegTree(A, lambda x, y: max(x, y), -f_inf)
	for _ in range(q):
		(t, *query) = map(int, input().split())
		if t == 1:
			(x, v) = query
			seg.update(x - 1, v)
		elif t == 2:
			(l, r) = query
			print(seg.query(l - 1, r))
		else:
			(x, v) = query
			(ok, ng) = (n + 1, x - 1)
			while abs(ng - ok) > 1:
				middle = (ok + ng) // 2
				if seg.query(x - 1, middle) >= v:
					ok = middle
				else:
					ng = middle
			print(ok)
resolve()


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
num = 2 ** (n - 1).bit_length()

def segfunc(x, y):
	return max(x, y)
seg = [0] * (2 * num - 1)
for i in range(n):
	seg[i + num - 1] = a[i]
for i in range(num - 2, -1, -1):
	seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

def update(i, x):
	i += num - 1
	seg[i] = x
	while i:
		i = (i - 1) // 2
		seg[i] = segfunc(seg[i * 2 + 1], seg[i * 2 + 2])

def query(l, r):
	l += num - 1
	r += num - 2
	if l == r:
		return seg[l]
	s = seg[l]
	l += 1
	while r - l > 1:
		if ~l % 2:
			s = segfunc(seg[l], s)
		if r % 2:
			s = segfunc(seg[r], s)
			r -= 1
		l //= 2
		r = (r - 1) // 2
	if l == r:
		return segfunc(s, seg[l])
	return segfunc(s, segfunc(seg[l], seg[r]))
for _ in range(q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		update(a - 1, b)
	if t == 2:
		print(query(a - 1, b))
	if t == 3:
		ng = a - 1
		ok = n + 1
		while ng + 1 != ok:
			mid = (ng + ok) // 2
			if query(ng, mid) >= b:
				ok = mid
			else:
				ng = mid
		print(ok)


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

class SegmentTree:

	def __init__(self, n, p, unit, f, g, h):
		num = 2 ** (n - 1).bit_length()
		seg = [unit] * (num * 2)
		self.lazy = [None] * (num * 2)
		for i in range(n):
			seg[num + i] = p[i]
		for i in range(num - 1, 0, -1):
			seg[i] = f(seg[i << 1], seg[(i << 1) + 1])
		self.num = num
		self.seg = seg
		self.unit = unit
		self.flag = False
		self.f = f
		self.g = g
		self.h = h

	def gindex(self, l, r):
		l += self.num
		r += self.num
		lm = l // (l & -l) >> 1
		rm = r // (r & -r) >> 1
		mm = max(lm, rm)
		r -= 1
		while l < r:
			if r <= rm:
				yield r
			if l <= lm:
				yield l
			l >>= 1
			r >>= 1
		while l:
			if l <= mm:
				yield l
			l >>= 1

	def propagates(self, ids):
		num = self.num
		g = self.g
		h = self.h
		for i in reversed(ids):
			v = self.lazy[i]
			if v is None:
				continue
			newv = (v[0] // 2, v[1] // 2)
			if i << 1 < num:
				self.lazy[i << 1] = h(self.lazy[i << 1], newv)
				self.lazy[(i << 1) + 1] = h(self.lazy[(i << 1) + 1], newv)
			self.seg[i << 1] = g(self.seg[i << 1], newv)
			self.seg[(i << 1) + 1] = g(self.seg[(i << 1) + 1], newv)
			self.lazy[i] = None

	def query(self, l, r):
		f = self.f
		if self.flag:
			(*ids,) = self.gindex(l, r)
			self.propagates(ids)
		ansl = ansr = self.unit
		l += self.num
		r += self.num - 1
		if l == r:
			return self.seg[l]
		while l < r:
			if l & 1:
				ansl = f(ansl, self.seg[l])
				l += 1
			if r & 1 == 0:
				ansr = f(self.seg[r], ansr)
				r -= 1
			l >>= 1
			r >>= 1
		if l == r:
			ansl = f(ansl, self.seg[l])
		return f(ansl, ansr)

	def update1(self, i, x):
		i += self.num
		f = self.f
		self.seg[i] = x
		while i:
			i >>= 1
			self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])

	def update2(self, l, r, x):
		self.flag = True
		(*ids,) = self.gindex(l, r)
		self.propagates(ids)
		num = self.num
		f = self.f
		g = self.g
		h = self.h
		l += num
		r += num - 1
		if l == r:
			self.seg[l] = g(self.seg[l], x)
			for i in ids:
				self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])
			return
		while l < r:
			if l & 1:
				if l < num:
					self.lazy[l] = h(self.lazy[l], x)
				self.seg[l] = g(self.seg[l], x)
				l += 1
			if r & 1 == 0:
				if r < num:
					self.lazy[r] = h(self.lazy[r], x)
				self.seg[r] = g(self.seg[r], x)
				r -= 1
			l >>= 1
			r >>= 1
			x = f(x, x)
		if l == r:
			self.lazy[l] = h(self.lazy[l], x)
			self.seg[l] = g(self.seg[l], x)
		for i in ids:
			self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1) + 1])

	def update(self, i, x):
		if type(i) is int:
			self.update1(i, x)
		else:
			self.update2(i[0], i[1], x)
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
f = lambda x, y: max(x, y)
seg = SegmentTree(n, a, 0, f, 0, 0)
for _ in range(q):
	(t, a, b) = map(int, input().split())
	if t == 1:
		seg.update(a - 1, b)
	if t == 2:
		print(seg.query(a - 1, b))
	if t == 3:
		ng = a - 1
		ok = n + 1
		while ng + 1 != ok:
			mid = (ng + ok) // 2
			if seg.query(ng, mid) >= b:
				ok = mid
			else:
				ng = mid
		print(ok)


def segfunc(x, y):
	return max(x, y)
ide_ele = 0

class segtree:

	def __init__(self, init_val, segfunc=segfunc, ide_ele=ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num + 1
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

def isok(mid, key):
	return st.query(x - 1, mid - 1) >= key

def b_search(x, key):
	ng = x - 1
	ok = n + 1
	while abs(ng - ok) > 1:
		mid = (ng + ok) // 2
		if isok(mid, key):
			ok = mid
		else:
			ng = mid
	return ok
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
st = segtree(a)
ans = []
for _ in range(q):
	(c, x, y) = map(int, input().split())
	if c == 1:
		st.update(x - 1, y)
	elif c == 2:
		ans += [st.query(x - 1, y - 1)]
	else:
		ans += [b_search(x, y)]
print(*ans, sep='\n')


class SegmentTree:

	def __init__(self, n, func, e, arrange=None):
		self.init(n)
		self.func = func
		self.e = e
		self.make_arrange(arrange)

	def init(self, n):
		self.inf = pow(2, 32)
		self.n = n
		self.N = 1
		while self.N < self.n:
			self.N *= 2
		self.size = self.N * 2

	def make_arrange(self, arrange):
		self.set_arrange(arrange)
		self.construct(arrange)

	def set_arrange(self, arrange):
		if arrange == None:
			self.segment = [self.e] * self.size
			return
		self.segment = [0] * self.N + arrange + [self.e] * (self.size - self.N - self.n)

	def construct(self, arrange):
		if arrange == None:
			return
		for i in range(self.N - 1, 0, -1):
			self.segment[i] = self.func(self.segment[2 * i], self.segment[2 * i + 1])

	def update(self, i, x):
		i += self.N - 1
		self.segment[i] = x
		while i > 1:
			i = i // 2
			self.segment[i] = self.func(self.segment[2 * i], self.segment[2 * i + 1])

	def count(self, l, r):
		res = self.e
		l += self.N - 1
		r += self.N
		while r > l:
			if l & 1:
				res = self.func(res, self.segment[l])
				l += 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segment[r])
			l >>= 1
			r >>= 1
		return res

	def bisect_sub(self, a, b, k, l, r, x):
		if r <= a or b <= l:
			return b + 1
		if self.segment[k] < x:
			return b + 1
		if k >= self.N:
			return r
		find_l = self.bisect_sub(a, b, 2 * k, l, (l + r) // 2, x)
		if find_l <= b:
			return find_l
		find_r = self.bisect_sub(a, b, 2 * k + 1, (l + r) // 2, r, x)
		return find_r

	def bisect(self, l, r, x):
		return self.bisect_sub(l - 1, r, 1, 0, self.size - self.N, x)

def main():
	(n, q) = map(int, input().split())
	p = list(map(int, input().split()))
	seg = SegmentTree(n, max, 0, arrange=p)
	res = []
	for i in range(q):
		(a, b, c) = list(map(int, input().split()))
		if a == 1:
			seg.update(b, c)
		elif a == 2:
			ans = seg.count(b, c)
			res.append(ans)
		else:
			ans = seg.bisect(b, n, c)
			res.append(ans)
	print(*res, sep='\n')
main()


class segtree:
	sta = -1
	func = max

	def __init__(self, n):
		self.n = n
		self.tree = [self.sta] * (2 * n)

	def build(self, list):
		for (i, x) in enumerate(list, self.n):
			self.tree[i] = x
		for i in range(self.n - 1, 0, -1):
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

	def set(self, i, x):
		i += self.n
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

	def get(self, l, r):
		l += self.n
		r += self.n
		res = self.sta
		while l < r:
			if l & 1:
				res = self.func(self.tree[l], res)
				l += 1
			if r & 1:
				res = self.func(self.tree[r - 1], res)
			l >>= 1
			r >>= 1
		return res

	def max_right(self, l, x):
		N = self.n

		def is_ok(v):
			return v < x

		def get_max(a, b):
			if a is None:
				return b
			if b is None:
				return a
			return max(a, b)
		v = None
		(i, node_l, node_w) = (l + N, l, 1)
		while True:
			if not i & 1:
				i >>= 1
				node_w <<= 1
				continue
			if node_l + node_w > N:
				break
			v1 = get_max(v, self.tree[i])
			if is_ok(v1):
				(v, i) = (v1, i + 1 >> 1)
				(node_l, node_w) = (node_l + node_w, node_w << 1)
			else:
				break
		(i, node_w) = (i << 1, node_w >> 1)
		while node_w:
			if node_l + node_w > N:
				(i, node_w) = (i << 1, node_w >> 1)
				continue
			v1 = get_max(v, self.tree[i])
			if is_ok(v1):
				(v, i) = (v1, i + 1 << 1)
				(node_l, node_w) = (node_l + node_w, node_w >> 1)
			else:
				(i, node_w) = (i << 1, node_w >> 1)
		i >>= 1
		return i - N
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
seg = segtree(n)
seg.build(a)
for _ in range(q):
	(t, x, v) = map(int, input().split())
	if t == 1:
		seg.set(x - 1, v)
	elif t == 2:
		print(seg.get(x - 1, v))
	else:
		print(seg.max_right(x - 1, v) + 1)


class LazySegmentTree:

	def __init__(self, n, f, g, h, ef, eh):
		self.n = n
		self.f = f
		self.g = lambda xh, x: g(xh, x) if xh != eh else x
		self.h = h
		self.ef = ef
		self.eh = eh
		l = (self.n - 1).bit_length()
		self.size = 1 << l
		self.tree = [self.ef] * (self.size << 1)
		self.lazy = [self.eh] * ((self.size << 1) + 1)
		self.plt_cnt = 0

	def built(self, array):
		for i in range(self.n):
			self.tree[self.size + i] = array[i]
		for i in range(self.size - 1, 0, -1):
			self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])

	def update(self, i, x):
		i += self.size
		self.propagate_lazy(i)
		self.tree[i] = x
		self.lazy[i] = self.eh
		self.propagate_tree(i)

	def get(self, i):
		i += self.size
		self.propagate_lazy(i)
		return self.g(self.lazy[i], self.tree[i])

	def update_range(self, l, r, x):
		if l >= r:
			return
		l += self.size
		r += self.size
		l0 = l // (l & -l)
		r0 = r // (r & -r)
		self.propagate_lazy(l0)
		self.propagate_lazy(r0 - 1)
		while l < r:
			if r & 1:
				r -= 1
				self.lazy[r] = self.h(x, self.lazy[r])
			if l & 1:
				self.lazy[l] = self.h(x, self.lazy[l])
				l += 1
			l >>= 1
			r >>= 1
		self.propagate_tree(l0)
		self.propagate_tree(r0 - 1)

	def get_range(self, l, r):
		l += self.size
		r += self.size
		self.propagate_lazy(l // (l & -l))
		self.propagate_lazy(r // (r & -r) - 1)
		res_l = self.ef
		res_r = self.ef
		while l < r:
			if l & 1:
				res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
				l += 1
			if r & 1:
				r -= 1
				res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
			l >>= 1
			r >>= 1
		return self.f(res_l, res_r)

	def max_right(self, l, z):
		if l >= self.n:
			return self.n
		l += self.size
		s = self.ef
		while 1:
			while l % 2 == 0:
				l >>= 1
			if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
				while l < self.size:
					l *= 2
					if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
						s = self.f(s, self.g(self.lazy[l], self.tree[l]))
						l += 1
				return l - self.size
			s = self.f(s, self.g(self.lazy[l], self.tree[l]))
			l += 1
			if l & -l == l:
				break
		return self.n

	def min_left(self, r, z):
		if r <= 0:
			return 0
		r += self.size
		s = self.ef
		while 1:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
				while r < self.size:
					r = r * 2 + 1
					if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
						s = self.f(self.g(self.lazy[r], self.tree[r]), s)
						r -= 1
				return r + 1 - self.size
			s = self.f(self.g(self.lazy[r], self.tree[r]), s)
			if r & -r == r:
				break
		return 0

	def propagate_lazy(self, i):
		for k in range(i.bit_length() - 1, 0, -1):
			x = i >> k
			if self.lazy[x] == self.eh:
				continue
			laz = self.lazy[x]
			self.lazy[x << 1 | 1] = self.h(laz, self.lazy[x << 1 | 1])
			self.lazy[x << 1] = self.h(laz, self.lazy[x << 1])
			self.tree[x] = self.g(laz, self.tree[x])
			self.lazy[x] = self.eh

	def propagate_tree(self, i):
		while i > 1:
			i >>= 1
			self.tree[i] = self.f(self.g(self.lazy[i << 1], self.tree[i << 1]), self.g(self.lazy[i << 1 | 1], self.tree[i << 1 | 1]))

	def __getitem__(self, i):
		return self.get(i)

	def __iter__(self):
		for x in range(1, self.size):
			if self.lazy[x] == self.eh:
				continue
			self.lazy[x << 1 | 1] = self.h(self.lazy[x], self.lazy[x << 1 | 1])
			self.lazy[x << 1] = self.h(self.lazy[x], self.lazy[x << 1])
			self.tree[x] = self.g(self.lazy[x], self.tree[x])
			self.lazy[x] = self.eh
		for (xh, x) in zip(self.lazy[self.size:self.size + self.n], self.tree[self.size:self.size + self.n]):
			yield self.g(xh, x)

	def __str__(self):
		return str(list(self))
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
ef = 0
eh = 0
f = lambda x, y: x if x > y else y
g = lambda x, y: x if x > y else y
h = lambda x, y: x if x > y else y
st = LazySegmentTree(N, f, g, h, ef, eh)
st.built(A)
res = []
for _ in range(Q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		st.update(x - 1, y)
	elif t == 2:
		res.append(st.get_range(x - 1, y))
	else:
		res.append(st.max_right(x - 1, lambda z: z < y) + 1)
print('\n'.join(map(str, res)))


import sys
from operator import ge

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)

class SegTree:

	def __init__(self, n, func, intv, A=[]):
		self.n = n
		self.func = func
		self.intv = intv
		n2 = 1
		while n2 < n:
			n2 <<= 1
		self.n2 = n2
		self.tree = [self.intv] * (n2 << 1)
		if A:
			for i in range(n):
				self.tree[n2 + i] = A[i]
			for i in range(n2 - 1, -1, -1):
				self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, x):
		i += self.n2
		self.tree[i] = x
		while i > 0:
			i >>= 1
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def add(self, i, x):
		self.update(i, self.get(i) + x)

	def query(self, a, b):
		l = a + self.n2
		r = b + self.n2
		s = self.intv
		while l < r:
			if r & 1:
				r -= 1
				s = self.func(s, self.tree[r])
			if l & 1:
				s = self.func(s, self.tree[l])
				l += 1
			l >>= 1
			r >>= 1
		return s

	def get(self, i):
		return self.tree[i + self.n2]

	def all(self):
		return self.tree[1]

	def bisearch_fore(self, l, r, x, func):
		ok = r + 1
		ng = l - 1
		while ng + 1 < ok:
			mid = (ok + ng) // 2
			if func(self.query(l, mid + 1), x):
				ok = mid
			else:
				ng = mid
		if ok != r + 1:
			return ok
		else:
			return INF

	def bisearch_back(self, l, r, x, func):
		ok = l - 1
		ng = r + 1
		while ok + 1 < ng:
			mid = (ok + ng) // 2
			if func(self.query(mid, r + 1), x):
				ok = mid
			else:
				ng = mid
		if ok != l - 1:
			return ok
		else:
			return -INF

	def print(self):
		for i in range(self.n):
			print(self.get(i), end=' ')
		print()
(N, Q) = MAP()
A = LIST()
seg = SegTree(N, max, -INF, A)
for _ in range(Q):
	(t, a, b) = MAP()
	if t == 1:
		a -= 1
		seg.update(a, b)
	elif t == 2:
		a -= 1
		b -= 1
		res = seg.query(a, b + 1)
		print(res)
	else:
		a -= 1
		res = seg.bisearch_fore(a, N - 1, b, ge)
		if res == INF:
			print(N + 1)
		else:
			print(res + 1)


class SegmentTree:

	def __init__(self, size, f=lambda x, y: min(x, y), idele=float('inf')):
		self.size = 2 ** (size - 1).bit_length()
		self.idele = idele
		self.f = f
		self.dat = [self.idele] * (self.size * 2)

	def update(self, i, x):
		i += self.size
		self.dat[i] = x
		while i > 0:
			i >>= 1
			self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

	def add(self, i, x):
		i += self.size
		self.dat[i] += x
		while i > 0:
			i >>= 1
			self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

	def query(self, l, r):
		l += self.size
		r += self.size
		(lres, rres) = (self.idele, self.idele)
		while l < r:
			if l & 1:
				lres = self.f(lres, self.dat[l])
				l += 1
			if r & 1:
				r -= 1
				rres = self.f(self.dat[r], rres)
			l >>= 1
			r >>= 1
		res = self.f(lres, rres)
		return res

	def lower_bound_index(self, i, v):
		i += self.size
		while self.dat[i] < v:
			if i & 1:
				if len(bin(i)) == len(bin(i + 1)):
					i += 1
				else:
					return self.size
			else:
				i >>= 1
		while i < self.size:
			if self.dat[2 * i] >= v:
				i = 2 * i
			else:
				i = 2 * i + 1
		return i - self.size

	def init(self, a):
		for (i, x) in enumerate(a):
			self.dat[i + self.size] = x
		for i in range(self.size - 1, -1, -1):
			self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
sgt = SegmentTree(n, lambda x, y: max(x, y), -float('inf'))
sgt.init(a)
for _ in range(q):
	(t, u, v) = map(int, input().split())
	if t == 1:
		sgt.update(u - 1, v)
	elif t == 2:
		print(sgt.query(u - 1, v))
	else:
		print(min(sgt.lower_bound_index(u - 1, v), n) + 1)


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
a = list(map(int, input().split()))

class SegTree:

	def segfunc(self, x, y):
		return max(x, y)

	def __init__(self, n, ide_ele, init_val):
		self.ide_ele = ide_ele
		self.num = 2 ** (n - 1).bit_length()
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res
seg = SegTree(N + 1, -1, [-1] + a)
for _ in range(Q):
	(t, x, v) = map(int, input().split())
	if t == 1:
		seg.update(x, v)
	if t == 2:
		print(seg.query(x, v + 1))
	if t == 3:
		ok = N + 1
		ng = x - 1
		while ok - ng > 1:
			m = (ok + ng) // 2
			if seg.query(x, m + 1) >= v:
				ok = m
			else:
				ng = m
		print(ok)


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

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

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):
	global WIDTH
	WIDTH = width
	set_depth((width - 1).bit_length() + 1)

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

def range_reduce(table, left, right, binop, unity):
	ret_left = unity
	ret_right = unity
	left += SEGTREE_SIZE // 2
	right += SEGTREE_SIZE // 2
	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 bisect_left(table, left, right, value):
	left += NONLEAF_SIZE
	right += NONLEAF_SIZE
	left_left = None
	right_left = None
	while left < right:
		if left & 1:
			if left_left is None and table[left] >= value:
				left_left = left
			left += 1
		if right & 1:
			if table[right - 1] >= value:
				right_left = right - 1
		left >>= 1
		right >>= 1
	if left_left is not None:
		pos = left_left
		while pos < NONLEAF_SIZE:
			if table[2 * pos] >= value:
				pos = 2 * pos
			else:
				pos = 2 * pos + 1
		return pos - NONLEAF_SIZE
	elif right_left is not None:
		pos = right_left
		while pos < NONLEAF_SIZE:
			if table[2 * pos] >= value:
				pos = 2 * pos
			else:
				pos = 2 * pos + 1
		return pos - NONLEAF_SIZE
	else:
		return WIDTH

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 main():
	(N, Q) = map(int, input().split())
	AS = list(map(int, input().split()))
	set_width(N)
	table = [0] * SEGTREE_SIZE
	table[NONLEAF_SIZE:NONLEAF_SIZE + len(AS)] = AS
	full_up(table, max)
	for _q in range(Q):
		(q, x, y) = map(int, input().split())
		if q == 1:
			point_set(table, x - 1, y, max)
		elif q == 2:
			print(range_reduce(table, x - 1, y, max, -INF))
		else:
			print(bisect_left(table, x - 1, N, y) + 1)
T1 = '\n5 5\n1 2 3 2 1\n2 1 5\n3 2 3\n1 3 1\n2 2 4\n3 1 3\n'
TEST_T1 = '\n>>> as_input(T1)\n>>> main()\n3\n3\n2\n6\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()


from typing import Callable, List, TypeVar
T = TypeVar('T')

class SegmentTree:
	__slots__ = ['e', 'op', '_n', '_size', 'tree']

	def __init__(self, a: List[T], e: T, op: Callable[[T, T], T]) -> None:
		self.e = e
		self.op = op
		self._n = len(a)
		self._size = 1 << (self._n - 1).bit_length()
		self.tree = [e] * self._size + a + [e] * (self._size - self._n)
		for i in range(self._size - 1, 0, -1):
			self._update(i)

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

	def set(self, k: int, x: T) -> None:
		assert 0 <= k < self._n
		k += self._size
		self.tree[k] = x
		while k:
			k >>= 1
			self._update(k)

	def get(self, k: int) -> T:
		assert 0 <= k < self._n
		return self.tree[k + self._size]

	def prod(self, l: int, r: int) -> T:
		assert 0 <= l <= r <= self._n
		(sml, smr) = (self.e, self.e)
		l += self._size
		r += self._size
		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) -> T:
		return self.tree[1]

	def max_right(self, l: int, f: Callable[[T], bool]) -> int:
		assert 0 <= l <= self._n
		assert f(self.e)
		if l == self._n:
			return self._n
		l += self._size
		sm = self.e
		while True:
			while not l & 1:
				l >>= 1
			if not f(self.op(sm, self.tree[l])):
				while l < self._size:
					l *= 2
					if f(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, f: Callable[[T], bool]) -> int:
		assert 0 <= r <= self._n
		assert f(self.e)
		if not r:
			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.tree[r], sm)):
				while r < self._size:
					r = 2 * r + 1
					if f(self.op(self.tree[r], sm)):
						sm = self.op(self.tree[r], sm)
						r -= 1
				return r + 1 - self._size
			if r & -r == r:
				break
		return 0
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
tree = SegmentTree(a, -1, max)
for _ in range(q):
	(t, x, y) = map(int, input().split())
	if t == 1:
		tree.set(x - 1, y)
	elif t == 2:
		print(tree.prod(x - 1, y))
	else:
		print(tree.max_right(x - 1, lambda n: n < y) + 1)


import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter
import sys
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(readline())

def read_int_n():
	return list(map(int, readline().split()))

def read_float():
	return float(readline())

def read_float_n():
	return list(map(float, readline().split()))

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

def read_str_n():
	return readline().strip().split()

def ep(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.perf_counter()
		ret = f(*args, **kwargs)
		e = time.perf_counter()
		ep(e - s, 'sec')
		return ret
	return wrap

class SegmentTree:

	def __init__(self, array, operator, identity_element):
		_len = len(array)
		self.__len = _len
		self.__op = operator
		self.__size = 1 << (_len - 1).bit_length()
		self.__tree = [identity_element] * self.__size + array + [identity_element] * (self.__size - _len)
		self.__ie = identity_element
		for i in range(self.__size - 1, 0, -1):
			self.__tree[i] = operator(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def update(self, i, v):
		i += self.__size
		self.__tree[i] = v
		while i:
			i //= 2
			self.__tree[i] = self.__op(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def query(self, l, r):
		l += self.__size
		r += self.__size
		ret = self.__ie
		while l < r:
			if l & 1:
				ret = self.__op(ret, self.__tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.__op(ret, self.__tree[r])
			l //= 2
			r //= 2
		return ret

	def max_right(self, l, f):
		if l == self.__len:
			return self.__len
		l += self.__size
		sm = self.__ie
		while True:
			while l % 2 == 0:
				l >>= 1
			if not f(self.__op(sm, self.__tree[l])):
				while l < self.__size:
					l = 2 * l
					if f(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.__len

	def __getitem__(self, key):
		return self.__tree[key + self.__size]

@mt
def slv(N, Q, A, T):
	st = SegmentTree(A, max, 0)
	ans = []
	for (t, x, y) in T:
		if t == 1:
			st.update(x - 1, y)
		elif t == 2:
			ans.append(st.query(x - 1, y))
		else:
			ans.append(st.max_right(x - 1, lambda x: x < y) + 1)
	return ans

def main():
	(N, Q) = read_int_n()
	A = read_int_n()
	T = [read_int_n() for _ in range(Q)]
	print(*slv(N, Q, A, T), sep='\n')
main()