Problem:


Score : 100 points

Problem Statement

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.

Sample Input 1

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

Sample Output 1

3
3
2
6

First query: Print 3, which is the maximum of (A_1,A_2,A_3,A_4,A_5)=(1,2,3,2,1).

Second query: Since 3>A_2, j=2 does not satisfy the condition．Since 3 \leq A_3, print j=3.

Third query: Replace the value of A_3 with 1. It becomes A=(1,2,1,2,1).

Fourth query: Print 2, which is the maximum of (A_2,A_3,A_4)=(2,1,2).

Fifth query: Since there is no j that satisfies the condition, print j=N+1=6.



Sample input:
5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 3


Sample output:
3
3
2
6

Submission status: Runtime Error

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__bit_code = """
def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x
"""

atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)


_atcoder_segtree_code = """
import typing

# import atcoder._bit


class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = atcoder._bit._ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [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: typing.Any) -> None:
        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: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, f: typing.Callable[[typing.Any], bool], 
                  left: int) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n

        left += self._size
        sm = self._e

        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int,
                 f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= right <= self._n
        assert f(self._e)

        if right == 0:
            return 0

        right += self._size
        sm = self._e

        first = True
        while first or (right & -right) != right:
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

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

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

# https://atcoder.jp/contests/practice2/tasks/practice2_j

import sys

# from atcoder.segtree import SegTree


def main() -> None:
    n, q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    segtree = SegTree(max, 0, 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(lambda v: v < y, x - 1) + 1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from typing import Callable, Iterator, TypeVar

S = TypeVar("S")


class SegmentTree:
    """Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
    """

    __slots__ = ["_e", "_op", "_n", "_size", "_tree"]

    def __init__(self, a: 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
        for i, a in enumerate(a, self._size):
            self._tree[i] = a
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self._tree[k] = self._op(self._tree[2 * k], self._tree[2 * k + 1])

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        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:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self._tree[k + self._size]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        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 op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self._tree[1]

    def max_right(self, l: int, f: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        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:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        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():
    # https://judge.yosupo.jp/problem/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():
    # https://atcoder.jp/contests/practice2/tasks/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():
    # https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A
    N, Q, *X = map(int, open(0).read().split())
    tree = SegmentTree([2 ** 31 - 1] * N, 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():
    # https://atcoder.jp/contests/abc125/tasks/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)


if __name__ == "__main__":
    staticrmq()
    # practice2_j()
    # dsl_2_a()
    # abc125_c()

Submission status: Runtime Error

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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+1] < x:
            return b+1
        if k >= self.N:
            return r
        
        find_l = self.bisect_sub(a, b, 2*k+1, l, (l+r)//2, x)
        if find_l <= b:
            return find_l

        find_r = self.bisect_sub(a, b, 2*k+2, (l+r)//2, r, x)
        return find_r

    def bisect(self, l, r, x):
        return self.bisect_sub(l-1, r, 0, 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")
            

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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
        r += self.N-1
        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+1] < x:
            return b+1
        if k >= self.N:
            return r
        
        find_l = self.bisect_sub(a, b, 2*k+1, l, (l+r)//2, x)
        if find_l <= b:
            return find_l

        find_r = self.bisect_sub(a, b, 2*k+2, (l+r)//2, r, x)
        return find_r

    def bisect(self, l, r, x):
        return self.bisect_sub(l-1, r, 0, 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(seg.segment)

    print(*res, sep="\n")
            

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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
        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+1] < x:
            return b+1
        if k >= self.N:
            return r
        
        find_l = self.bisect_sub(a, b, 2*k+1, l, (l+r)//2, x)
        if find_l <= b:
            return find_l

        find_r = self.bisect_sub(a, b, 2*k+2, (l+r)//2, r, x)
        return find_r

    def bisect(self, l, r, x):
        return self.bisect_sub(l-1, r, 0, 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")
            

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
"""
セグメント木
func：二項演算の関数（モノイドである必要あり）
e：単位元（モノイドにおける）
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
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 - 1
        self.N -= 1
    
    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, -1, -1):
            self.segment[i] = self.func(self.segment[2*i+1], self.segment[2*i+2])
    
    def update(self, i, x):
        i += (self.N-1)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.func(self.segment[2*i+1], self.segment[2*i+2])
    

    def count(self, l, r):
        res = self.e
        l += self.N-1
        r += self.N-2
        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
    
    """
    二分探索
    これは区間[l, r]にてx以上となる最小のインデックスを返すメソッド
    まずfind_l：二分木左側を探索し、そこに条件を満たすものがなかったらfind_：右側を探索
    インデックスの最大最小により左右を使い分ける
    """

    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+1, l, (l+r)//2, x)
        if find_l <= b:
            return find_l

        find_r = self.bisect_sub(a, b, 2*k+2, (l+r)//2, r, x)
        return find_r

    def bisect(self, l, r, x):
        return self.bisect_sub(l-1, r, 0, 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")
            

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from typing import Callable, List, TypeVar

S = TypeVar("S")


class SegmentTree:
    """Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
    """

    __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:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        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:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        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 op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        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:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        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


# https://atcoder.jp/contests/practice2/tasks/practice2_j
import sys

readline = sys.stdin.buffer.readline

N, Q = map(int, readline().split())
(*A,) = map(int, readline().split())
tree = SegmentTree(A, 0, 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)))