output_description: For each query with T_i=2, 3, print the answer.
  
  * * *
input_description: 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
attempt: mod = 1000000007
  eps = 10**-9
  
  
  def main():
      import sys
  
      input = sys.stdin.buffer.readline
  
      class SegmentTree:
          def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
              self.N = len(A)
              self.LV = (self.N - 1).bit_length()
              self.N0 = 1 << self.LV
              self.segfunc = segfunc
              self.ident = ident
              if initialize:
                  self.data = (
                      [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                  )
                  for i in range(self.N0 - 1, 0, -1):
                      self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
              else:
                  self.data = [self.ident] * (self.N0 * 2)
  
          def update(self, i, x):
              i += self.N0 - 1
              self.data[i] = x
              for _ in range(self.LV):
                  i >>= 1
                  self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])
  
          # open interval [l, r)
          def query(self, l, r):
              l += self.N0 - 1
              r += self.N0 - 1
              ret_l = self.ident
              ret_r = self.ident
              while l < r:
                  if l & 1:
                      ret_l = self.segfunc(ret_l, self.data[l])
                      l += 1
                  if r & 1:
                      ret_r = self.segfunc(self.data[r - 1], ret_r)
                      r -= 1
                  l >>= 1
                  r >>= 1
              return self.segfunc(ret_l, ret_r)
  
          # return smallest i(l <= i < r) s.t. check(A[i]) == True
          def binsearch(self, l, r, check):
              if not check(self.query(l, r)):
                  return r
              l += self.N0 - 1
              val = self.ident
              while True:
                  if check(self.segfunc(val, self.data[l])):
                      break
                  if l & 1:
                      val = self.segfunc(val, self.data[l])
                      l += 1
                  l >>= 1
              while l < self.N0:
                  newval = self.segfunc(val, self.data[l * 2])
                  if not check(newval):
                      val = newval
                      l = (l << 1) + 1
                  else:
                      l <<= 1
              return l - self.N0 + 1
  
      def check(val):
          return val >= v
  
      N, Q = map(int, input().split())
      A = list(map(int, input().split()))
  
      ST = SegmentTree(A, segfunc=max, ident=-2000000000)
      for _ in range(Q):
          t, x, v = map(int, input().split())
          if t == 1:
              ST.update(x, v)
          elif t == 2:
              l = x
              r = v + 1
              print(ST.query(l, r))
          else:
              print(ST.binsearch(x, N + 1, check))
  
  
  if __name__ == "__main__":
      main()
  
problem_description: 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.
samples: [{"input": "5 5\n    1 2 3 2 1\n    2 1 5\n    3 2 3\n    1 3 1\n    2 2 4\n    3 1 3", "output": "3\n    3\n    2\n    6\n    \n\n  * First query: Print 3, which is the maximum of (A_1,A_2,A_3,A_4,A_5)=(1,2,3,2,1).\n  * Second query: Since 3>A_2, j=2 does not satisfy the condition\uff0eSince 3 \\leq A_3, print j=3.\n  * Third query: Replace the value of A_3 with 1. It becomes A=(1,2,1,2,1).\n  * Fourth query: Print 2, which is the maximum of (A_2,A_3,A_4)=(2,1,2).\n  * Fifth query: Since there is no j that satisfies the condition, print j=N+1=6."}]