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 = list(map(int, input().split()))

A = list(map(int, input().split()))



st = SegmentTree(A, max, 0)

res = list()



for _ in range(Q):

    t, x, y = list(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))))
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):

        #assert len(arr) <= self.n

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

        #assert 0 <= 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):

        #assert 0 <= p < self.n

        return self.d[p + self.size]



    def prod(self, l, r):

        #assert 0 <= l <= r <= self.n

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

        #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 * 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):

        #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: break

        return 0



import sys

input = sys.stdin.buffer.readline



N, Q = list(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 = list(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))))
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 = list(map(int, input().split()))
A = list(map(int, input().split()))
st = SegmentTree(A, max, 0)
res = list()
for _ in range(Q):
    t, x, y = list(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))))

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):
        # assert len(arr) <= self.n
        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):
        # assert 0 <= 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):
        # assert 0 <= p < self.n
        return self.d[p + self.size]

    def prod(self, l, r):
        # assert 0 <= l <= r <= self.n
        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):
        # 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 * 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):
        # 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:
                break
        return 0


import sys

input = sys.stdin.buffer.readline
N, Q = list(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 = list(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))))

-    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 __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 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 update(self, k): +        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 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) +    def build(self, arr): +        # assert len(arr) <= self.n +        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): +        # assert 0 <= 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): +        # assert 0 <= p < self.n +        return self.d[p + self.size] + +    def prod(self, l, r): +        # assert 0 <= l <= r <= self.n +        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): +        # 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 * 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): +        # 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: +                break +        return 0 -A = list(map(int, input().split())) -st = SegmentTree(A, max, 0) -res = list() +A = tuple(map(int, input().split())) +st = SegmentTree(N, max, 0) +st.build(A) +res = [] -        res.append(st.query(x - 1, y)) +        res.append(st.prod(x - 1, y)) -        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) +        res.append(st.max_right(x - 1, lambda z: z < y) + 1)