-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE DerivingVia                #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE UndecidableInstances       #-}
{-# LANGUAGE FlexibleContexts       #-}
import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive      (PrimMonad, PrimState)
import           Control.Monad.ST
import           Data.Bits
import qualified Data.ByteString.Char8        as BS
import           Data.Char                    (isSpace)
import           Data.Coerce
import qualified Data.Foldable
import           Data.Int                     (Int64)
import           Data.List                    (unfoldr)
import           Data.Monoid                  hiding (Max, Min)
import           Data.Reflection
import           Data.Semigroup
import           Data.Type.Coercion
import qualified Data.Vector                  as V
import qualified Data.Vector.Generic          as G
import qualified Data.Vector.Generic.Mutable  as GM
import qualified Data.Vector.Mutable          as VM
import qualified Data.Vector.Unboxing         as U
import qualified Data.Vector.Unboxing.Mutable as UM
import qualified Test.QuickCheck              as QC
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 $ fromVector_SegTree (U.coerceVector xs0 :: U.Vector (Max Int))
  itree <- asUnboxedSegTree $ fromVector_SegTree (U.imap (\i x -> Min (i, x)) xs0 :: U.Vector (Min (Int, Int)))
  -- (Min (Arg n 0))
  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 (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 (i, x)) b@(Min (j, y))
                          | x < v && y < v = monoidIdentity
                          | x < v = b
                          | y < v = a
                          | i <= j = a
                          | otherwise = b
                        monoidIdentity = Min (n, v)
                    Min (j, v) <- reifyMonoidF monoidOp monoidIdentity
                      (\_ -> let itree' = coerceSegTree (unsafeCoerce (Coercion :: Coercion () ())) itree -- TODO
                             in queryRange_SegTree itree' (x - 1) n
                      ) ()
                    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)

reifyMonoidF :: Functor f => (a -> a -> a) -> a -> (forall s. Reifies s (ReifiedMonoid a) => t -> f (ReflectedMonoid a s)) -> t -> f a
reifyMonoidF mop mid action t = reify (ReifiedMonoid mop mid) $ unreflectedMonoidF (action t)
  where
    unreflectedMonoidF :: Functor f => f (ReflectedMonoid a s) -> proxy s -> f a
    unreflectedMonoidF m _ = (\(ReflectedMonoid x) -> x) <$> m

--
-- 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 :: (Monoid 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
    let !two_l_minus_1 = (1 `shiftL` l) - 1
    forM_ [0..two_l_minus_1] $ \k -> do
      x <- GM.read mvec ((1 `shiftL` (l + 1)) + 2 * k - 1)
      y <- GM.read mvec ((1 `shiftL` (l + 1)) + 2 * k)
      GM.write mvec (two_l_minus_1 + k) $! x <> y
  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 7
-- 3
-- >>> ceil_log2 8
-- 3
ceil_log2 :: Int -> Int
ceil_log2 0 = 0
ceil_log2 x = finiteBitSize x - countLeadingZeros (x - 1)

--
-- Debugging
--

runSegTree :: (forall s. ST s (SegTree VM.MVector s a)) -> (Int, V.Vector a)
runSegTree m = runST $ do
  SegTree depth mvec <- m
  vec <- V.freeze mvec
  return (depth, vec)

fromVector_SegTree_naive :: (Monoid a, G.Vector vec a, PrimMonad m) => vec a -> m (SegTree (G.Mutable vec) (PrimState m) a)
fromVector_SegTree_naive vec = do
  tree <- new_SegTree (G.length vec)
  G.imapM_ (update_SegTree tree) vec
  return tree

prop_fromVector_SegTree :: [String] -> QC.Property
prop_fromVector_SegTree xs = let vec = V.fromList xs
                             in runSegTree (fromVector_SegTree vec) QC.=== runSegTree (fromVector_SegTree_naive vec)

prop_queryRange_SegTree :: [String] -> QC.Property
prop_queryRange_SegTree xs = let vec = V.fromList xs
                             in QC.forAll (QC.choose (0,V.length vec)) $ \i -> QC.forAll (QC.choose (i,V.length vec)) $ \j ->
                             let lhs = runST $ do
                                   tree <- asBoxedSegTree $ fromVector_SegTree vec
                                   queryRange_SegTree tree i j
                             in lhs QC.=== Data.Foldable.fold (V.slice i (j - i) vec)
