{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE LambdaCase   #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bits
import qualified Data.ByteString.Builder     as B
import qualified Data.ByteString.Char8       as C
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import           Data.Monoid
import           Data.Monoid
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Data.Word
import qualified System.IO                   as IO

main :: IO ()
main = do
    [n, q] <- map read.words <$> getLine :: IO [Int]
    queries <- U.unfoldrN q parseInt3 <$> C.getContents
    B.hPutBuilder IO.stdout
        . U.foldr (\x acc -> B.intDec x <> B.char7 '\n' <> acc) mempty
        $ solve n queries

solve :: Int -> U.Vector (Int, Int, Int) -> U.Vector Int
solve n queries = runSegTree (U.replicate n mempty) queries

runSegTree :: U.Vector Int -> U.Vector (Int, Int, Int) -> U.Vector Int
runSegTree vec queries = U.create $ do
    seg <- _SEGfromVector vec
    res <- UM.replicate (U.length queries) mempty
    size <- U.foldM' (\acc -> \case
            (0, k, v) -> do
                _SEGupdate k v seg
                return acc
            (1, l, r) -> do
                _SEGquery l (r + 1) seg >>= UM.unsafeWrite res acc
                return $ acc + 1
        ) 0 queries
    return $ UM.take size res

instance Monoid Int where
    mempty = 0x7fffffff
    mappend = min
    {-# INLINE mempty #-}
    {-# INLINE mappend #-}

-------------------------------------------------------------------------------
extendToPowerOfTwo :: Int -> Int
extendToPowerOfTwo x = head . filter (x <=) $ map bit [0..]
-- extendToPowerOfTwo x
--     | w > 1 = fromIntegral
--         $ unsafeShiftR (maxBound :: Word) (countLeadingZeros (w - 1)) + 1
--     | otherwise = 1
--   where
--     w :: Word
--     w = fromIntegral x

newtype SegTree m a = SegTree { unSegTree :: UM.MVector m a }

-- | O(n)
_SEGfromVector
    :: (Monoid a, U.Unbox a, PrimMonad m, Applicative m)
    => U.Vector a -> m (SegTree (PrimState m) a)
_SEGfromVector vec = do
    let n = extendToPowerOfTwo $ U.length vec
    tree <- UM.replicate (2 * n) mempty
--    U.imapM_ (UM.unsafeWrite tree . (+ n)) vec
    U.mapM_ (uncurry $ UM.unsafeWrite tree . (+ n)) $ U.zip (U.generate n id) vec
    rev (n - 1) $ \i -> do
        x <- mappend
            <$> UM.unsafeRead tree (i .<<. 1)
            <*> UM.unsafeRead tree (i .<<. 1 .|. 1)
        UM.unsafeWrite tree i x
    return $ SegTree tree
  where
    rev :: (Monad m) => Int -> (Int -> m ()) -> m ()
    rev n = U.forM_ $ U.iterateN n (subtract 1) (n - 1)
    {-# INLINE rev #-}
    infixl 8 .<<.
    (.<<.) :: Int -> Int -> Int
    (.<<.) = unsafeShiftL
    {-# INLINE (.<<.) #-}

-- | O(log n)
_SEGupdate
    :: (Monoid a, U.Unbox a, PrimMonad m, Applicative m)
    => Int -> a -> SegTree (PrimState m) a -> m ()
_SEGupdate k v segtree = do
    let tree = unSegTree segtree
    let n = UM.length tree .>>. 1
    UM.unsafeWrite tree (k + n) v
    flip fix (k + n) $ \loop !i ->
        when (i > 1) $ do
            x <- mappend
                <$> UM.unsafeRead tree i
                <*> UM.unsafeRead tree (i .^. 1)
            UM.unsafeWrite tree (i .>>. 1) x
            loop $ unsafeShiftR i 1
  where
    infixl 8 .>>.
    (.>>.) :: Int -> Int -> Int
    (.>>.) = unsafeShiftR
    {-# INLINE (.>>.) #-}
    infixl 6 .^.
    (.^.) :: Int -> Int -> Int
    (.^.) = xor
    {-# INLINE (.^.) #-}

-- | mappend [l..r) O(log n)
_SEGquery
    :: (Monoid a, U.Unbox a, PrimMonad m, Applicative m)
    => Int -> Int -> SegTree (PrimState m) a -> m a
_SEGquery l r segtree = do
    let tree = unSegTree segtree
    let n = UM.length tree .>>. 1
    let stepL l
            | l .&. 1 == 1 = \acc ->
                mappend acc <$> UM.unsafeRead tree l
            | otherwise = return

        stepR r
            | r .&. 1 == 1 = \acc ->
                mappend acc <$> UM.unsafeRead tree (r - 1)
            | otherwise = return

        go l r k
            | l < r = go ((l + l .&. 1) .>>. 1) ((r - r .&. 1) .>>. 1)
                $ stepL l >=> (stepR r >=> k)
            | otherwise = k
    go (n + l) (n + r) return mempty
  where
    infixl 8 .>>.
    (.>>.) :: Int -> Int -> Int
    (.>>.) = unsafeShiftR
    {-# INLINE (.>>.) #-}

type Parser a = C.ByteString -> Maybe (a, C.ByteString)

parseInt :: Parser Int
parseInt = C.readInt . C.dropWhile isSpace

parseInt2 :: Parser (Int, Int)
parseInt2 = runStateT $
    (,) <$> StateT (C.readInt . C.dropWhile isSpace)
        <*> StateT (C.readInt . B.unsafeTail)

parseInt3 :: Parser (Int, Int, Int)
parseInt3 = runStateT $
    (,,) <$> StateT (C.readInt . C.dropWhile isSpace)
        <*> StateT (C.readInt . B.unsafeTail)
        <*> StateT (C.readInt . B.unsafeTail)




Measured memory_bytes: 12088