use proconio::input;

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
        tq: [(usize, usize, usize); q],
    }
    let mut segtree = SegmentTree::new(a, || std::usize::MIN, |&a, &b| a.max(b));
    for (t, x, y) in tq {
        match t {
            1 => segtree.update(x - 1, y),
            2 => println!("{}", segtree.query(x - 1, y)),
            3 => println!(
                "{}",
                segtree.bisect_left(x - 1, n, |&ai| ai >= y).unwrap_or(n) + 1
            ),
            _ => unreachable!(),
        }
    }
}

struct SegmentTree<T, F, E>
where
    F: Fn(&T, &T) -> T,
    E: Fn() -> T,
{
    n: usize,            // size of data
    f: F,                // binary operation of the monoid
    e: E,                // identity element of the monoid
    binary_tree: Vec<T>, // 1-indexed binary tree (parent: x/2, left_child: x*2, right_child: x*2+1, sibling: x^1, is_x_left_child: x%2==0, is_x_right_child: x%2==1)
}
impl<T, F, E> SegmentTree<T, F, E>
where
    F: Fn(&T, &T) -> T,
    E: Fn() -> T,
{
    /// O(n) # create segment tree, note that this method requires ownership of data.
    fn new(data: Vec<T>, e: E, f: F) -> Self {
        let (n, binary_tree) = (
            data.len(),
            (0..2 * data.len().next_power_of_two())
                .map(|_| e())
                .collect(),
        );
        let segment_tree = SegmentTree {
            n,
            f,
            e,
            binary_tree,
        };
        segment_tree.init(data)
    }

    /// O(n) # init segment tree by given data.
    fn init(mut self, data: Vec<T>) -> Self {
        let leaf_offset = self.leaf_offset();
        for (i, di) in data.into_iter().enumerate() {
            self.binary_tree[leaf_offset + i] = di;
        }
        for i in (1..leaf_offset).rev() {
            self.binary_tree[i] = (self.f)(&self.binary_tree[i * 2], &self.binary_tree[i * 2 + 1]);
        }
        self
    }

    /// O(1) # get beginning index of the segment tree leaf.
    fn leaf_offset(&self) -> usize {
        self.n.next_power_of_two()
    }

    /// O(log(n)) # set leaf[k] = x, and update segment tree. (non-recursive)
    fn update(&mut self, k: usize, x: T) {
        let mut current = self.leaf_offset() + k;
        self.binary_tree[current] = x;
        while current / 2 > 0 {
            current /= 2;
            self.binary_tree[current] = (self.f)(
                &self.binary_tree[current * 2],
                &self.binary_tree[current * 2 + 1],
            );
        }
    }

    /// O(log(n)) # calculate f(l, l+1, ..., r-1). note the half interval [l, r). (non-recursive)
    fn query(&self, l: usize, r: usize) -> T {
        let (mut li, mut ri) = (self.leaf_offset() + l, self.leaf_offset() + r);
        let (mut result_left, mut result_right) = ((self.e)(), (self.e)());
        while li < ri {
            if li % 2 == 1 {
                result_left = (self.f)(&result_left, &self.binary_tree[li]);
                li += 1; // l is right child, so move to next subtree.
            }
            if ri % 2 == 1 {
                result_right = (self.f)(&self.binary_tree[ri ^ 1], &result_right);
            }
            li /= 2;
            ri /= 2;
        }
        (self.f)(&result_left, &result_right)
    }

    /// O(log^2(n)) # search the leftmost leaf where cmp(x) is true.
    fn bisect_left<C>(&self, l: usize, r: usize, cmp: C) -> Option<usize>
    where
        C: Fn(&T) -> bool,
    {
        let (mut from, mut to) = (l, r);
        while to - from > 1 {
            let mid = (from + to) / 2;
            if cmp(&self.query(from, mid)) {
                to = mid;
            } else {
                from = mid;
            }
        }
        if cmp(&self.binary_tree[self.leaf_offset() + from]) {
            Some(from)
        } else {
            None
        }
    }
}


Measured memory_bytes: 17716