import Control.Monad
import Control.Monad.ST
import qualified Data.ByteString.Char8 as C
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM

main = C.interact $ put . sol . get

get = U.unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.pack . unlines . fmap show . U.toList

sol v = runST $ do
  h <- UM.replicate (10^5+1) 0
  U.forM_ as $ UM.unsafeModify h (+ 1)
  r <- UM.unsafeNew q
  forM_ [0..q-1] $ \i -> do
    if i==0
      then UM.unsafeWrite r i $ U.sum as 
      else UM.unsafeRead r (i-1) >>= UM.unsafeWrite r i
    let (b,c) = (qs U.! (2*i),qs U.! (2*i+1))
    cnt <- UM.unsafeRead h b
    UM.unsafeWrite h b 0
    UM.unsafeModify h (+ cnt) c
    UM.unsafeModify r (+ (cnt*(c-b))) i
  U.unsafeFreeze r
  where
  n = v U.! 0
  as = U.slice 1 n v
  q = v U.! (n+1)
  qs = U.unsafeDrop (n+2) v