-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE UndecidableInstances #-}
import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive      (PrimMonad, PrimState)
import           Data.Bits
import qualified Data.ByteString.Char8        as BS
import           Data.Char                    (isSpace)
import           Data.Coerce
import           Data.Int                     (Int64)
import           Data.List                    (unfoldr)
import           Data.Monoid                  hiding (Max, Min)
import           Data.Reflection              (ReflectedMonoid (..),
                                               ReifiedMonoid (..), reify)
import           Data.Semigroup
import           Data.Type.Coercion
import qualified Data.Vector.Generic          as G
import qualified Data.Vector.Generic.Mutable  as GM
import qualified Data.Vector.Unboxing         as U
import qualified Data.Vector.Unboxing.Mutable as UM
import           Unsafe.Coerce

main = do
  [n,q] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  xs0 <- U.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  tree <- asUnboxedSegTree $ new_SegTree n
  itree <- asUnboxedSegTree $ new_SegTree' n (Min (Arg n 0))
  U.imapM_ (update_SegTree tree) (U.coerceVector xs0 :: U.Vector (Max Int)) -- TODO: Efficient initialization
  U.imapM_ (update_SegTree itree) (U.imap (\i x -> Min (Arg i x)) xs0 :: U.Vector (ArgMin Int Int)) -- TODO: Efficient initialization
  replicateM_ n $ do
    qs <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    case qs of
      [1,x,v] -> do update_SegTree tree (x - 1) (Max v)
                    update_SegTree itree (x - 1) (Min (Arg (x - 1) v))
      [2,l,r] -> do Max v <- queryRange_SegTree tree (l - 1) (r - 1)
                    print v
      [3,x,v] -> do let monoidOp a@(Min (Arg i x)) b@(Min (Arg j y))
                          | x < v && y < v = monoidIdentity
                          | x < v = b
                          | y < v = a
                          | i <= j = a
                          | otherwise = b
                        monoidIdentity = Min (Arg n v)
                        reifiedMonoid = ReifiedMonoid monoidOp monoidIdentity
                        unreflectedMonoidF :: Functor f => f (ReflectedMonoid a s) -> proxy s -> f a
                        unreflectedMonoidF m _ = (\(ReflectedMonoid x) -> x) <$> m
                    Min (Arg j v) <- reify reifiedMonoid $ \proxy ->
                      let itree' = coerceSegTree (unsafeCoerce (Coercion :: Coercion () ())) itree -- TODO
                      in unreflectedMonoidF (queryRange_SegTree itree' (x - 1) n) proxy
                    print (j + 1)
      _ -> error "Invalid query"

-- orphan instances
deriving newtype instance U.Unboxable a => U.Unboxable (ReflectedMonoid a s)
deriving via U.Generics (Arg a b) instance (U.Unboxable a, U.Unboxable b) => U.Unboxable (Arg a b)

coerceSegTree :: Coercion (UM.MVector s a) (UM.MVector s b) -> SegTree UM.MVector s a -> SegTree UM.MVector s b
coerceSegTree c (SegTree depth v) = SegTree depth (coerceWith c v)

--
-- Segment Tree
--

data SegTree mvec s a = SegTree {-# UNPACK #-} !Int !(mvec s a)

-- index: zero-based
queryAt_SegTree :: (GM.MVector mvec a, PrimMonad m) => SegTree mvec (PrimState m) a -> Int -> m a
queryAt_SegTree (SegTree depth vec) !i = GM.read vec ((1 `shiftL` depth) - 1 + i)
{-# INLINE queryAt_SegTree #-}

-- index: zero-based
-- queryRange_SegTree i j tree == mconcat <$> sequence [queryAt_SegTree tree k | k <- [i..j-1]]
queryRange_SegTree :: (Monoid a, GM.MVector mvec a, PrimMonad m) => SegTree mvec (PrimState m) a -> Int -> Int -> m a
queryRange_SegTree (SegTree depth vec) !i !j | i < j = doQuery 0 depth i j
                                             | otherwise = return mempty
  where
    -- Invariant: 0 <= k*2^l <= i < j <= (k+1)*2^l <= 2^depth
    doQuery !k 0 !i !j | i == k, j == k+1 = GM.read vec ((1 `shiftL` depth) - 1 + k)
                       | otherwise = error "queryRange"
    doQuery !k l !i !j | i == k `shiftL` l, j == (k+1) `shiftL` l = GM.read vec ((1 `shiftL` (depth-l)) - 1 + k)
                       | m <= i = doQuery (2*k+1) (l-1) i j
                       | j <= m = doQuery (2*k) (l-1) i j
                       | otherwise = liftA2 (<>) (doQuery (2*k) (l-1) i m) (doQuery (2*k+1) (l-1) m j)
      where m = (2*k+1) `shiftL` (l-1)
{-# INLINE queryRange_SegTree #-}

-- index: zero-based
update_SegTree :: (Semigroup a, GM.MVector mvec a, PrimMonad m) => SegTree mvec (PrimState m) a -> Int -> a -> m ()
update_SegTree (SegTree depth vec) !i !x = loop ((1 `shiftL` depth) + i) x
  where
    loop 1 !x = GM.write vec 0 x
    loop !j !x = do
      GM.write vec (j - 1) x
      y <- if even j
           then (x <>) <$> GM.read vec j
           else (<> x) <$> GM.read vec (j - 2)
      loop (j `shiftR` 1) y
{-# INLINE update_SegTree #-}

new_SegTree :: (Monoid a, GM.MVector mvec a, PrimMonad m) => Int -> m (SegTree mvec (PrimState m) a)
new_SegTree n = do let depth = ceil_log2 n
                   vec <- GM.replicate ((1 `shiftL` (depth + 1)) - 1) mempty
                   return (SegTree depth vec)
{-# INLINE new_SegTree #-}

new_SegTree' :: (GM.MVector mvec a, PrimMonad m) => Int -> a -> m (SegTree mvec (PrimState m) a)
new_SegTree' n e = do let depth = ceil_log2 n
                      vec <- GM.replicate ((1 `shiftL` (depth + 1)) - 1) e
                      return (SegTree depth vec)
{-# INLINE new_SegTree' #-}

{-
fromVector_SegTree :: (Semigroup a, G.Vector vec a, PrimMonad m) => vec a -> m (SegTree (G.Mutable vec) (PrimState m) a)
fromVector_SegTree v = do
  let !n = G.length v
      !depth = ceil_log2 n
  mvec <- GM.replicate ((1 `shiftL` (depth + 1)) - 1) mempty
  G.copy (GM.slice ((1 `shiftL` depth) - 1) n mvec) v
  forM_ [depth - 1, depth - 2 .. 0] $ \l -> do
    ...
  return (SegTree depth mvec)
-}

{-
asBoxedSegTree :: (PrimMonad m) => m (SegTree VM.MVector (PrimState m) a) -> m (SegTree VM.MVector (PrimState m) a)
asBoxedSegTree = id
-}

asUnboxedSegTree :: (PrimMonad m) => m (SegTree UM.MVector (PrimState m) a) -> m (SegTree UM.MVector (PrimState m) a)
asUnboxedSegTree = id

ceil_log2 :: Int -> Int
ceil_log2 0 = 0
ceil_log2 x = finiteBitSize x - countLeadingZeros (x - 1)
