--[[------------------------------------------------------------------------]]--
--- `0 <= num <= 10^8` 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

--- `1 <= index < len`
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
	assert(0 <= vec_len and vec_len <= 100000000)
	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])`を、
--- モノイドの性質を満たしていると仮定して計算します。
--- `O(log(n))`
function SegTree:operate_between(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:operate_all()
	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:search_to_right_from(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`の値が入ります。
--- `init_val_fn()`の値を含む範囲が`true`になるようにする(題意の`not`にあたる？)
--- `segtree`の上で二分探索をします。`right`が小さくなる方向に調べていきます
--- `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
		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 + 1 - len
		end
		value = operation_fn(vec[right], value)
		right = right - 1

		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
)

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)
	elseif t == 2 then
		local l_i, r_i = read("n", "n")
		insert(out_t, segTree:operate_between(l_i, r_i))
	else
		local x_i, v_i = read("n", "n")
		insert(
			out_t,
			segTree:search_to_right_from(x_i, function(x) return x < v_i end)
		)
	end
end

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


Measured memory_bytes: 30024