import Data.Ord
import Data.List

main :: IO ()
main = interact $ unlines . map (show' . uncurry allr) . read' . lines
 where
  read' ("0 0":_) = []
  read' (_:r:xs) = (l,qs) : read' xs''
   where
    (l',(q:xs')) = splitAt (read r) xs
    (qs',xs'') = splitAt (read q) xs'
    l = map ((\[t,n,m,_] -> R (read t) (read n) (read m)) . words) l'
    qs = map ((\[ts,te,mq] -> Q (P (read ts) (read te)) (read mq)) . words) qs'
  show' = init . unlines . map show

data Record = R {t::Time, n::Pid, m::Uid} deriving (Eq, Ord)
data Question = Q {pq::Period, mq::Uid} deriving (Eq, Ord)
data Period = P {ts::Time, te::Time} deriving (Eq, Ord)

unionp :: Period -> Period -> Maybe Period
unionp p1 p2
 | te p1 < ts p2 = Nothing
 | te p2 < ts p1 = Nothing
 | ts p1 >= ts p2 && te p1 <= te p2 = Just p2
 | ts p1 <= ts p2 && te p1 >= te p2 = Just p1
 | ts p1 <= ts p2 && te p1 >= ts p2 = Just (P (ts p1) (te p2))
 | ts p2 <= ts p1 && te p2 >= ts p1 = Just (P (ts p2) (te p1))

unionsum :: [Period] -> Period
unionsum ps = P (minimum ps') (maximum ps')
 where ps' = map ts ps ++ map te ps

intersectp :: Period -> Period -> Maybe Period
intersectp p1 p2
 | te p1 < ts p2 = Nothing
 | te p2 < ts p1 = Nothing
 | ts p1 >= ts p2 && te p1 <= te p2 = Just p1
 | ts p1 <= ts p2 && te p1 >= te p2 = Just p2
 | ts p1 <= ts p2 && te p1 >= ts p2 = Just (P (ts p2) (te p1))
 | ts p2 <= ts p1 && te p2 >= ts p1 = Just (P (ts p1) (te p2))

time :: Period -> Time
time p = (te p) - (ts p)

type Log = [Record]
type Time = Int
type Pid = Int
type Uid = Int

allr :: Log -> [Question] -> [Time]
allr l = map (analyze l)

analyze :: Log -> Question -> Time
analyze l q = count (period (query (mq q) l)) (pq q)

count :: [Period] -> Period -> Time
count ps p = sum $ map (maybe 0 time . intersectp p) (map unionsum ps')
 where ps' = groupBy overlap (sort ps)

overlap :: Period -> Period -> Bool
overlap p1 p2 = unionp p1 p2 /= Nothing

period :: Log -> [Period]
period = map (\[x,y] -> P x y) . groupAt 2 . map t . sortBy (comparing n)

query :: Uid -> Log -> Log
query x = filter ((==x) . m)

groupAt :: Int -> [a] -> [[a]]
groupAt n xs
 | null xs = []
 | otherwise = take n xs : groupAt n (drop n xs)