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
#####################################################################################################
##### Lazy Propotional Segment tree (遅延区間比例セグメント木)
#####################################################################################################

"""
区間更新、区間取得が可能

セグ木の深さ毎でモノイド間の作用 g の振る舞いが異なってしまう場合がある。
実際のところ、作用 g は大域的作用である必要はなく、時間効率そのままで局所変数を一つ持たせて局所化することができる。
ただし、一般化された分配法則
g[i](x*y) = g[i<<1]x * g[(i<<1)|1]x
を満たす必要がある。

以下の例では、 セグ木の i 番目のノードを構成する要素の数（何個の要素の積か？）を l[i] として、
g[i]x = x*l[i]
という局所作用を考えている。

例)

RSQ and RUQ:
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4777823#2

# クエリ関数
ef = 0
f = lambda x, y : x+y
# 更新関数
eh = -(1<<24)
h = lambda x, y: x if x != eh else y
g = lambda x, y, l: x*l

#################################################################################
#################################################################################


解説
https://maspypy.com/segment-tree-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B72
https://smijake3.hatenablog.com/entry/2018/11/03/100133

解説（作用付きモノイド）
https://algo-logic.info/segment-tree/

参考コード（C++）
https://ei1333.github.io/library/library/structure/segment-tree/lazy-segment-tree.cpp.html

参考コード(python)
https://yukicoder.me/submissions/470340


"""


class LazyPropSegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        :param length: 添え字 i がいくつの要素を畳み込んだ値になっているか
        """
        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):
        """
        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):
        """
        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):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        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):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        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):
        """
        [l, r)の区間取得の結果を返す　(0-indexed)
        """
        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):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        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):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        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):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        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])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            lazy[x] = eh

    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        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)))