--[[------------------------------------------------------------------------]]--
--- `0 <= num <= 1<<61` return minimum non-negative `x` s.t. `n <= 2**x`
local function ceil_pow2(num)
	local x = 0
	while (1 << x) < num do
		x = x + 1
	end
	return x
end

--- index >= 1
local function update(_, index)
	_.vec[index] = _.operation_fn(
		_.vec[2 * index], _.vec[2 * index + 1]
	)
end

local SegTree ={}

--- 0 <= #element_count_or_vec <= 10^8
--- (1): 長さelement_count_or_vecの数列vecを作ります。初期値は全部init_val_fn()です。
--- (2): 長さ#element_count_or_vecの数列vecを作ります。
--- element_count_or_vecの内容が初期値となります。
--- O(n)
function SegTree.new(operation_fn, init_val_fn, element_count_or_vec)
	if type(element_count_or_vec) == "number" then
		assert(
			0 <= #element_count_or_vec
				and #element_count_or_vec <= 100000000
		)
		local vec = {}
		for i = 1, element_count_or_vec do
			vec[i] = init_val_fn()
		end
		return SegTree.new(operation_fn, init_val_fn, vec)
	end
	assert(
		type(element_count_or_vec) == "table",
		"arg error! need number or table"
	)
	local vec_len = #element_count_or_vec
	local log = ceil_pow2(vec_len)
	local len = 1 << log
	local vec = {}
	local _ = {
		vec_len = vec_len,
		log = log,
		len = len,
		vec = vec,
		operation_fn = operation_fn,
		init_val_fn = init_val_fn,
		update = update
	}
	for i = 1, 2 * len do
		vec[i] = init_val_fn()
	end
	for i = 1, vec_len do
		vec[len + i - 1] = element_count_or_vec[i];
	end
	for i = len - 1, 1, -1 do
		update(_, i)
	end
	return setmetatable({_ = _}, {__index = SegTree})
end

--- 1 <= index <= #element_count_or_vec
--- vec[index]にvalueを代入します。
--- O(log(n))
function SegTree:set(index, value)
	assert(1 <= index and index <= self._.vec_len)
	index = index - 1 + self._.len
	self._.vec[index] = value
	for i = 1, self._.log do
		update(self._, index >> i)
	end
end

--- 1 <= index <= #element_count_or_vec
--- vec[index]を返します。
--- O(1)
function SegTree:get(index)
	assert(1 <= index and index <= self._.vec_len)
	return self._.vec[index - 1 + self._.len]
end

--- 1 <= left <= right <= #element_count_or_vec
--- operation_fn(vec[left], ..., vec[right])を、
--- モノイドの性質を満たしていると仮定して計算します。l = r のときはe()を返します。
--- O(log(n))
function SegTree:prod(left, right)
	assert(1 <= left and left <= right and right <= self._.vec_len)
	local vec = self._.vec
	local operation_fn = self._.operation_fn

	left = left - 1 + self._.len
	right = right - 1 + self._.len
	local operated_left = vec[left]
	local operated_right = vec[right]
	while left < right do
		-- 今のleftが奇数のときつまり引数のleftが偶数のとき
		if left & 1 == 1 then
			operated_left = operation_fn(operated_left, vec[left])
			left = left + 1
		end
		if right & 1 == 1 then
			right = right - 1
			operated_right = operation_fn(vec[right], operated_right)
		end
		left = left >> 1
		right = right >> 1
	end
	return operation_fn(operated_left, operated_right)
end

--- op(a[1], ..., a[n])を計算します。n = 0のときはinit_val_fn()を返します。
--- O(1)
function SegTree:all_prod()
	return self._.vec[1]
end

--- 1 <= left <= #element_count_or_vec
--- 関数bool_fn_arg_val(x) -> bool を定義する必要があります。xはvecの値が入ります。
--- init_val_fn()の値を含む範囲がtrueになるようにする(題意のnotにあたる)
--- segtreeの上で二分探索をします。leftから大きくなる方向に調べていきます。
--- O(log(n))
function SegTree:max_right(left, bool_fn_arg_val)
	assert(1 <= left and left <= self._.vec_len)
	assert(bool_fn_arg_val(self._.init_val_fn()))
	local operation_fn = self._.operation_fn
	local vec = self._.vec
	local len = self._.len

	left = left - 1 + len
	local value = self._.init_val_fn()
	while true do
		while left % 2 == 0 do
			left = left >> 1
		end
		if not bool_fn_arg_val(operation_fn(value, vec[left])) then
			while left < len do
				left = 2 * left
				if bool_fn_arg_val(operation_fn(value, vec[left])) then
					value = operation_fn(value, vec[left])
					left = left + 1
				end
			end
			return left + 1 - len
		end
		value = operation_fn(value, vec[left])
		left = left + 1

		if (left & -left) == left then
			return self._.vec_len + 1
		end
	end
end

--- 1 <= right <= #element_count_or_vec
--- 関数bool_fn_arg_val(x) -> bool を定義する必要があります。xはvecの値が入ります。
--- segtreeの上で二分探索をします。
--- O(log(n))
function SegTree:min_left(right, bool_fn_arg_val)
	assert(1 <= right and right <= self._.vec_len)
	assert(bool_fn_arg_val(self._.init_val_fn())) --
	local operation_fn = self._.operation_fn
	local vec = self._.vec
	local len = self._.len

	right = right - 1 + len
	local value = self._.init_val_fn()
	while true do
		right = right - 1
		while right > 1 and right % 2 == 1 do
			right = right >> 1
		end
		if not bool_fn_arg_val(operation_fn(vec[right], value)) then
			while right < len do
				right = 2 * right + 1
				if bool_fn_arg_val(operation_fn(vec[right], value)) then
					value = operation_fn(vec[right], value)
					right = right + 1
				end
			end
			return right - len
		end
		value = operation_fn(vec[right], value)

		if (right & -right) == right then
			return 0
		end
	end
end

--[[------------------------------------------------------------------------]]--

local read = io.read
local insert = table.insert

local n, q = read("n", "n")
local a_t = {}
for i = 1, n do
	a_t[i] = read("n")
end

local segTree = SegTree.new(
	math.max,
	function() return -1 end,
	a_t
)
--print(table.concat(segTree._.vec, ", "))

local out_t = {}
for i = 1, q do
	local t = read("n")
	if t == 1 then
		local x_i, v_i = read("n", "n")
		segTree:set(x_i, v_i)
--print(table.concat(segTree._.vec, ", "))
	elseif t == 2 then
		local l_i, r_i = read("n", "n")
		insert(out_t, segTree:prod(l_i, r_i))
	else
		local x_i, v_i = read("n", "n")
		insert(
			out_t,
			segTree:max_right(x_i, function(x) return x < v_i end)
		)
	end
end

print(table.concat(out_t, "\n"))


Measured memory_bytes: 30056