{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE TypeFamilies #-}

module Main where

import           Control.Monad
import           Control.Monad.Extra
import           Control.Monad.Primitive
import qualified Data.Array as A
import qualified Data.Array.IO as AIO
import qualified Data.Array.Unboxed as AU
import           Data.Bits
import           Data.Bool
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BSC8
import           Data.Char
import           Data.Either
import           Data.Function
import qualified Data.Graph.Inductive.Graph as G
import qualified Data.Graph.Inductive.PatriciaTree as G
import qualified Data.Heap as H
import           Data.Int
import           Data.List
import qualified Data.Map.Strict as M
import           Data.Maybe
import           Data.Monoid
import           Data.Ord
import           Data.Semigroup
import qualified Data.Sequence as SQ
import qualified Data.Set as S
import           Data.Time
import           Data.Tuple
import qualified Data.Vector as V
import           Data.Vector.Algorithms.Search
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector.Unboxing as VUG
import qualified Data.Vector.Unboxing.Mutable as VUGM
import           Debug.Trace
import           GHC.Stack

main :: IO ()
main = do
  --aN       <- getI
  --[aA, aB] <- getIL
  --aS       <- getLine
  [aN, aQ] <- getIL
  let aa = VU.generate aN id
  lazySegTree@(LazySegTree (d, _, _, _, _, _, _, _))
    <- getLazySegTree aa (\x -> Rars (1, 1, x)) m c i
  --print =<< V.freeze d
  replicateM_ aQ
    $ do
      aQ <- getVUI
      VU.mapM
        (\i
         -> lazySegTreeApplyPoint lazySegTree i (S.singleton ((aQ VU.! 2), i)))
        $ VU.enumFromN (pred $ aQ VU.! 0) ((aQ VU.! 1) - (aQ VU.! 0) + 1)
      Rars (num1, dig1, left1) <- lazySegTreeAllProd lazySegTree
      print num1
  --print =<< V.freeze d
  return ()
  where
    m :: S.Set (Int, Int) -> Rars -> Rars
    m s r@(Rars (num, dig, left)) =
      let nnum = foldl
            (\tnum (d, p) -> let rp = p - left
                                 aa = dig - rp
                                 bb = div num (10 ^ (aa - 1))
                                 cc = (bb - (10 * (div bb 10)))
                             in num + (d - cc) * 10 ^ (aa - 1))
            num
            $ S.toList s
      in Rars (nnum, dig, left)

    c :: S.Set (Int, Int) -> S.Set (Int, Int) -> S.Set (Int, Int)
    c l r = l <> r

    i :: S.Set (Int, Int)
    i = S.empty

newtype Rars = Rars (Int, Int, Int)
  deriving Show

instance Semigroup Rars where
  Rars (num1, dig1, left1) <> Rars (num2, dig2, left2) = Rars
    (num1 * (10 ^ dig2) + num2, dig1 + dig2, left1)

instance Monoid Rars where
  mempty = Rars (0, 0, 0)

data LazySegTree a b =
  LazySegTree ( VM.IOVector a
                , VM.IOVector b
                , Int
                , Int
                , Int
                , (b -> a -> a)
                , (b -> b -> b)
                , b)

getLazySegTree :: (PrimMonad m, Monoid a, VU.Unbox t, PrimState m ~ RealWorld)
               => VU.Vector t
               -> (t -> a)
               -> (b -> a -> a)
               -> (b -> b -> b)
               -> b
               -> m (LazySegTree a b)
getLazySegTree v op m c i = do
  let lenV = VU.length v
  let log = ceilPow2 lenV
  let size = shiftL 1 log
  d <- VM.replicate (2 * size) mempty
  lz <- VM.replicate size i
  V.mapM_ (\i -> VM.write d (size + i) (op $ v VU.! i)) $ V.enumFromN 0 lenV
  V.mapM_ (\i -> lazySegTreeUpdate d i)
    $ V.enumFromStepN (size - 1) (-1) (size - 1)
  return $ LazySegTree (d, lz, lenV, size, log, m, c, i)

lazySegTreeSet :: (PrimMonad m, Monoid a, PrimState m ~ RealWorld)
               => LazySegTree a b
               -> Int
               -> a
               -> m ()
lazySegTreeSet (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i)) p x
  | p < 0 || n <= p = error
    "lazySegTreeSet:pの値を0以上元配列の長さより小さい値に見直してください。"
  | otherwise = do
    let np = p + size
    VM.write d np x
    V.mapM_ (\i -> lazySegTreePush (LazySegTree lazySegTree) (shiftR np i))
      $ V.enumFromStepN log (-1) log
    V.mapM_ (\i -> lazySegTreeUpdate d (shiftR np i)) $ V.enumFromN 1 log
    return ()

segTreeGet :: (PrimMonad m, Monoid b1, PrimState m ~ RealWorld)
           => LazySegTree b1 b2
           -> Int
           -> m b1
segTreeGet (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i)) p
  | p < 0 || n <= p = error
    "lazySegTreeGet:pの値を0以上元配列の長さより小さい値に見直してください。"
  | otherwise = do
    let np = p + size
    V.mapM_ (\i -> lazySegTreePush (LazySegTree lazySegTree) (shiftR np i))
      $ V.enumFromStepN log (-1) log
    VM.read d np

lazySegTreeProd :: (Monoid a, PrimMonad m, PrimState m ~ RealWorld)
                => LazySegTree a b
                -> Int
                -> Int
                -> m a
lazySegTreeProd (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i)) l r
  | l < 0 || r < l || n < r = error
    "lazySegTreeProd:l,rの値を0以上元配列の長さより小さい値に見直してください。"
  | otherwise =
    if l == r
    then return mempty
    else do
      let nl = l + size
      let nr = r + size
      V.mapM_
        (\i -> do
           _ <- if ((shiftL (shiftR nl i) i) /= nl)
                then lazySegTreePush (LazySegTree lazySegTree) (shiftR nl i)
                else return ()
           if ((shiftL (shiftR nr i) i) /= nr)
             then lazySegTreePush (LazySegTree lazySegTree) (shiftR nr i)
             else return ())
        $ V.enumFromStepN log (-1) log
      lazySegTreeProdP (LazySegTree lazySegTree) nl nr mempty mempty

lazySegTreeProdP
  :: (Monoid a, PrimMonad m, PrimState m ~ RealWorld)
  => LazySegTree a b
  -> Int
  -> Int
  -> a
  -> a
  -> m a
lazySegTreeProdP
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  l
  r
  sml
  smr
  | r <= l = return $ sml <> smr
  | otherwise = do
    (nsml, nl) <- if (l .&. 1) /= 0
                  then do
                    dl <- VM.read d l
                    let nl = l + 1
                    return $ (sml <> dl, nl)
                  else return (sml, l)
    (nsmr, nr) <- if (r .&. 1) /= 0
                  then do
                    let nr = r - 1
                    dr <- VM.read d nr
                    return $ (dr <> smr, nr)
                  else return (smr, r)
    lazySegTreeProdP
      (LazySegTree lazySegTree)
      (shiftR nl 1)
      (shiftR nr 1)
      nsml
      nsmr

lazySegTreeAllProd (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i)) =
  VM.read d 1

lazySegTreeApplyPoint :: (PrimMonad m, Monoid a, PrimState m ~ RealWorld)
                      => LazySegTree a b
                      -> Int
                      -> b
                      -> m ()
lazySegTreeApplyPoint
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  p
  f
  | p < 0 || n < p = error
    "lazySegTreeApply:pの値を0以上元配列の長さより小さい値に見直してください。"
  | otherwise = do
    let np = p + size
    V.mapM_ (\i -> lazySegTreePush (LazySegTree lazySegTree) (shiftR np i))
      $ V.enumFromStepN log (-1) log
    dp <- VM.read d np
    VM.write d np (m f dp)
    V.mapM_ (\i -> lazySegTreeUpdate d (shiftR np i)) $ V.enumFromN 1 log

lazySegTreeApplyLR :: (PrimMonad m, Monoid a, PrimState m ~ RealWorld)
                   => LazySegTree a b
                   -> Int
                   -> Int
                   -> b
                   -> m ()
lazySegTreeApplyLR
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  l
  r
  f
  | l < 0 || r < l || n < r = error
    "lazySegTreeApplyLR:l,rの値を0以上元配列の長さより小さい値に見直してください。"
  | otherwise =
    if l == r
    then return ()
    else do
      let nl = l + size
      let nr = r + size
      V.mapM_
        (\i -> do
           _ <- if ((shiftL (shiftR nl i) i) /= nl)
                then lazySegTreePush (LazySegTree lazySegTree) (shiftR nl i)
                else return ()
           if ((shiftL (shiftR nr i) i) /= nr)
             then lazySegTreePush (LazySegTree lazySegTree) (shiftR (nr - 1) i)
             else return ())
        $ V.enumFromStepN log (-1) log
      lazySegTreeApplyLRP (LazySegTree lazySegTree) nl nr f
      V.mapM_
        (\i -> do
           _ <- if ((shiftL (shiftR nl i) i) /= nl)
                then lazySegTreeUpdate d (shiftR nl i)
                else return ()
           if ((shiftL (shiftR nr i) i) /= nr)
             then lazySegTreeUpdate d (shiftR (nr - 1) i)
             else return ())
        $ V.enumFromN 1 log

lazySegTreeApplyLRP
  :: (PrimMonad m, Monoid a, PrimState m ~ RealWorld)
  => LazySegTree a b
  -> Int
  -> Int
  -> b
  -> m ()
lazySegTreeApplyLRP
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  l
  r
  f =
  if r <= l
  then return ()
  else do
    nl <- if (l .&. 1) /= 0
          then do
            lazySegTreeAllApply (LazySegTree lazySegTree) l f
            return $ l + 1
          else return l
    nr <- if (r .&. 1) /= 0
          then do
            lazySegTreeAllApply (LazySegTree lazySegTree) (r - 1) f
            return $ r - 1
          else return r
    lazySegTreeApplyLRP (LazySegTree lazySegTree) (shiftR nl 1) (shiftR nr 1) f

lazySegTreeMaxRight :: (Monoid t, PrimMonad m, PrimState m ~ RealWorld)
                    => LazySegTree t b
                    -> Int
                    -> (t -> Bool)
                    -> m Int
lazySegTreeMaxRight
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  l
  f
  | l < 0 || n < l = error
    "segTreeMaxRight:rの値を0以上元配列の長さより小さい値に見直してください。"
  | f mempty == False = error
    "segTreeMaxRight:fを単位元に適用した場合にTrueになる関数に見直してください。"
  | otherwise =
    if l == n
    then return n
    else let nl = l + size
         in lazySegTreeMaxRightP2 (LazySegTree lazySegTree) f mempty nl

lazySegTreeMaxRightP1 :: (Integral p, Bits p) => p -> p
lazySegTreeMaxRightP1 l = if mod l 2 == 0
                          then lazySegTreeMaxRightP1 $ shiftR l 1
                          else l

lazySegTreeMaxRightP2
  :: (PrimMonad m, Monoid t, PrimState m ~ RealWorld)
  => LazySegTree t b
  -> (t -> Bool)
  -> t
  -> Int
  -> m Int
lazySegTreeMaxRightP2
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  f
  sm
  l = do
  let nl = lazySegTreeMaxRightP1 l
  dl <- VM.read d nl
  if (f $ sm <> dl) == False
    then lazySegTreeMaxRightP3 (LazySegTree lazySegTree) f sm nl
    else if (nl + 1) .&. negate (nl + 1) == nl + 1
         then return n
         else lazySegTreeMaxRightP2
           (LazySegTree lazySegTree)
           f
           (sm <> dl)
           (nl + 1)

lazySegTreeMaxRightP3
  :: (PrimMonad m, Monoid a, PrimState m ~ RealWorld)
  => LazySegTree a b
  -> (a -> Bool)
  -> a
  -> Int
  -> m Int
lazySegTreeMaxRightP3
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  f
  sm
  l
  | size <= l = return $ l - size
  | otherwise = do
    let nl = 2 * l
    dl <- VM.read d nl
    if (f $ sm <> dl) == True
      then lazySegTreeMaxRightP3
        (LazySegTree lazySegTree)
        f
        (sm <> dl)
        (nl + 1)
      else lazySegTreeMaxRightP3 (LazySegTree lazySegTree) f sm nl

--未実行未テスト
lazySegTreeMinLeft :: (Monoid t, PrimMonad m, PrimState m ~ RealWorld)
                   => LazySegTree t b
                   -> Int
                   -> (t -> Bool)
                   -> m Int
lazySegTreeMinLeft (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i)) r f
  | r < 0 || n < r = error
    "segTreeMinLeft:rの値を0以上元配列の長さより小さい値に見直してください。"
  | f mempty == False = error
    "segTreeMinLeft:fを単位元に適用した場合にTrueになる関数に見直してください。"
  | otherwise = if r == 0
                then return 0
                else let nr = r + size
                     in lazySegTreeMinLeftP2
                          (LazySegTree lazySegTree)
                          f
                          mempty
                          (lazySegTreeMinLeftP1 nr)

lazySegTreeMinLeftP1 :: (Integral p, Bits p) => p -> p
lazySegTreeMinLeftP1 r = if r > 1 && ((mod r 2) /= 0)
                         then lazySegTreeMinLeftP1 $ shiftR r 1
                         else r

lazySegTreeMinLeftP2
  :: (PrimMonad m, Monoid t, PrimState m ~ RealWorld)
  => LazySegTree t b
  -> (t -> Bool)
  -> t
  -> Int
  -> m Int
lazySegTreeMinLeftP2
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  f
  sm
  r = do
  let nr = lazySegTreeMinLeftP1 (r - 1)
  dr <- VM.read d r
  if (f $ dr <> sm) == False
    then lazySegTreeMinLeftP3 (LazySegTree lazySegTree) f sm r
    else if r .&. negate r == r
         then return n
         else lazySegTreeMinLeftP2 (LazySegTree lazySegTree) f (dr <> sm) (r)

lazySegTreeMinLeftP3
  :: (PrimMonad m, Monoid a, PrimState m ~ RealWorld)
  => LazySegTree a b
  -> (a -> Bool)
  -> a
  -> Int
  -> m Int
lazySegTreeMinLeftP3
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  f
  sm
  r
  | size <= r = return $ r + 1 - size
  | otherwise = do
    let nr = 2 * r + 1
    dr <- VM.read d r
    if (f $ dr <> sm) == True
      then lazySegTreeMinLeftP3 (LazySegTree lazySegTree) f (dr <> sm) (nr - 1)
      else lazySegTreeMinLeftP3 (LazySegTree lazySegTree) f sm nr

lazySegTreeUpdate
  :: (PrimMonad m, Monoid a) => VM.MVector (PrimState m) a -> Int -> m ()
lazySegTreeUpdate d k = do
  d2k <- VM.read d (2 * k)
  d2k1 <- VM.read d (2 * k + 1)
  VM.write d k (d2k <> d2k1)
  return ()

lazySegTreeAllApply :: (PrimMonad m, Monoid a1, PrimState m ~ RealWorld)
                    => LazySegTree a1 a2
                    -> Int
                    -> a2
                    -> m ()
lazySegTreeAllApply
  (LazySegTree lazySegTree@(d, lz, n, size, log, m, c, i))
  k
  f = do
  dk <- VM.read d k
  VM.write d k $ m f dk
  if k < size
    then do
      lzk <- VM.read lz k
      VM.write lz k $ (c lzk f)
    else return ()

lazySegTreePush :: (PrimMonad m, Monoid a, PrimState m ~ RealWorld)
                => LazySegTree a b
                -> Int
                -> m ()
lazySegTreePush (LazySegTree lazySegTree) k = do
  let (d, lz, n, size, log, m, c, i) = lazySegTree
  lzk <- VM.read lz k
  lazySegTreeAllApply (LazySegTree lazySegTree) (2 * k) lzk
  lzk <- VM.read lz k
  lazySegTreeAllApply (LazySegTree lazySegTree) (2 * k + 1) lzk
  VM.write lz k i

ceilPow2 n = ceilPow2p n 0

ceilPow2p n x = if shiftL 1 x < n
                then ceilPow2p n (x + 1)
                else x

modulus = 998244353

newtype MInt = M Int

instance VUG.Unboxable MInt where
  type Rep MInt = Int

instance Num MInt where
  (M a) + (M b) = M $ mod (a + b) modulus

  (M a) - (M b) = M $ mod (a - b) modulus

  (M a) * (M b) = M $ mod (a * b) modulus

  fromInteger a = M $ mod (fromInteger a) modulus

  abs (M a) = undefined

  signum (M a) = undefined

instance Show MInt where
  show (M a) = show (mod a modulus)

int2MInt :: Int -> MInt
int2MInt a = M (mod a modulus)

mInt2Int :: MInt -> Int
mInt2Int (M a) = a

instance Eq MInt where
  (M a) == (M b) = a == b

instance Ord MInt where
  (M a) <= (M b) = a <= b

--雑多系
t :: Int -> (Int, Int)
t x = (x, 1)

i def f t = bool t def $ f t

shiftRCnt k = shiftRCntP k 1

shiftRCntP k c = let nk = shiftR k 1
                 in if nk == 0
                    then c
                    else shiftRCntP nk (c + 1)

myVUmap f vu =
  if vu == VU.empty
  then VU.empty
  else VU.unfoldr
    (\x -> let ret = f $ VU.head x
               tailx = VU.tail x
           in if x == VU.empty
              then Nothing
              else if isLeft ret
                   then Just (either id id ret, tailx)
                   else Just (either id id ret, VU.empty))
    vu

myVUmapM f vu =
  if vu == VU.empty
  then return VU.empty
  else VU.unfoldrM
    (\x -> do
       ret <- f $ VU.head x
       let tailx = VU.tail x
       if x == VU.empty
         then return Nothing
         else if isLeft ret
              then return $ Just (either id id ret, tailx)
              else return $ Just (either id id ret, VU.empty))
    vu

myVUmapM_ f vu =
  if vu == VU.empty
  then return ()
  else do
    ret1 <- VU.unfoldrM
      (\x -> do
         ret2 <- f $ VU.head x
         let tailx = VU.tail x
         if x == VU.empty
           then return Nothing
           else if isLeft ret2
                then return $ Just (either id id ret2, tailx)
                else return $ Just (either id id ret2, VU.empty))
      vu
    return ()

myVUfor vu f = myVUmap f vu

myVUforM vu f = myVUmapM f vu

myVUforM_ vu f = myVUmapM_ f vu

myVUfoldl f acc vu =
  if vu == VU.empty
  then return acc
  else do
    let ret = f acc (VU.head vu)
    if isLeft ret
      then myVUfoldl f (either id id ret) (VU.tail vu)
      else return $ either id id ret

myVUfoldr f acc vu =
  if vu == VU.empty
  then return acc
  else do
    let ret = f acc (VU.last vu)
    if isLeft ret
      then myVUfoldr f (either id id ret) (VU.init vu)
      else return $ either id id ret

myVUfoldM f acc vu =
  if vu == VU.empty
  then return acc
  else do
    ret <- f acc (VU.head vu)
    if isLeft ret
      then myVUfoldM f (either id id ret) (VU.tail vu)
      else return $ either id id ret

--周りのマス
aroundSquare y x h w = VU.concatMap
  (\a -> VU.mapMaybe
     (\b -> let ya = y + a
                xb = x + b
            in if abs a + abs b == 1
               then if ya < 0 || ya >= h || xb < 0 || xb >= w
                    then Nothing
                    else Just (ya, xb)
               else Nothing)
   $ VU.enumFromN (-1) 3)
  $ VU.enumFromN (-1) 3

--入力系
splitReadBSC8 :: BSC8.ByteString -> [Int]
splitReadBSC8 bs = let (bs1, newBs) = BSC8.splitAt 1 bs
                   in if newBs == BSC8.empty
                      then [test $ BSC8.readInt bs1]
                      else test (BSC8.readInt bs1):splitReadBSC8 newBs
  where
    test (Just (i, _)) = i

read2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> IO Char
read2DimChar vec y x = do
  vecY <- VM.read vec y
  VUM.read vecY x

write2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> Char -> IO ()
write2DimChar vec y x t = do
  vecY <- VM.read vec y
  VUM.write vecY x t

readTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> IO Int
readTwoDimVec vec y x = do
  vecY <- VM.read vec y
  VUM.read vecY x

writeTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> Int -> IO ()
writeTwoDimVec vec y x t = do
  vecY <- VM.read vec y
  VUM.write vecY x t

getVUI :: IO (VU.Vector Int)
getVUI = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine

getRepVUI :: Int -> IO (VU.Vector Int)
getRepVUI n = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) . BSC8.unlines
  <$> replicateM n BSC8.getLine

getVS :: IO (V.Vector Char)
getVS = V.fromList <$> getLine

getVUC :: IO (VU.Vector Char)
getVUC = VU.fromList <$> getLine

readI :: BSC8.ByteString -> Int
readI = fst . fromJust . BSC8.readInt

readInteger :: BSC8.ByteString -> Integer
readInteger = fst . fromJust . BSC8.readInteger

readIL :: BSC8.ByteString -> [Int]
readIL = map readI . BSC8.words

readIT2 :: BSC8.ByteString -> (Int, Int)
readIT2 bs = let words = BSC8.words bs
             in (readI $ head words, readI $ last words)

readIT3 :: BSC8.ByteString -> (Int, Int, Int)
readIT3 bs = let words = BSC8.words bs
             in (readI $ head words, readI $ words !! 1, readI $ words !! 2)

getI :: IO Int
getI = readI <$> BSC8.getLine

getInteger :: IO Integer
getInteger = readInteger <$> BSC8.getLine

getIL :: IO [Int]
getIL = readIL <$> BSC8.getLine

getIT2 :: IO (Int, Int)
getIT2 = readIT2 <$> BSC8.getLine

getIT3 :: IO (Int, Int, Int)
getIT3 = readIT3 <$> BSC8.getLine

getIT2Order :: IO (Int, Int)
getIT2Order = getIL
  >>= \x@[xz, xo] -> if xz > xo
                     then return (xo, xz)
                     else return (xz, xo)

getNIS :: Int -> IO [(Int, BSC8.ByteString)]
getNIS 0 = return []
getNIS n = do
  [aFst, aSnd] <- BSC8.words <$> BSC8.getLine
  next <- getNIS (n - 1)
  return ((readI aFst, aSnd):next)

il2Words :: [Int] -> String
il2Words = unwords . map show

il2Lines :: [Int] -> String
il2Lines = unlines . map show