import Control.Monad
import Data.List
import qualified Data.Map as Map
import qualified Data.Set as Set
import qualified Data.Array as Arr
import System.Random
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)

f::[[Int]]->[(Int,Int)]
f []=[]
f ((l:r:[]):xs)=(l,r): f xs


f4 :: [(Int,Int)]->Map.Map (Int,Int) Int->[String]
f4 [] _=[]
f4 ((l1,r1):qs) ms=if not (Map.lookup (l1,r1) ms==Nothing) then
                          let (Just x)=Map.lookup (l1,r1) ms
                          in (show x):f4 qs ms
                   else "0":f4 qs ms

f5 :: Int->[(Int,Int)]->[(Int,[Int])]->[(Int,[Int])]
f5 _ [] zs=zs
f5 p1 ((l1,r1):xs) []=f5 p1 xs [(l1,[r1])] 
f5 p1 xs2@((l1,r1):xs) zs2@((z1,z2):zs)
    |p1<l1=f5 l1 xs2 ((l1,[]):zs2)
    |p1>l1=f5 p1 xs zs2
    |p1==l1=f5 p1 xs $ ((z1,(r1:z2)):zs)

f6 :: [(Int,[Int])]->[(Int,[Int])]->[(Int,Int)]->[((Int,Int),Int)]->[((Int,Int),Int)]
f6 _ [] _ zs=zs
f6 [] ((l2,rs2):qs) cs zs=let zs2=f9 l2 0 (reverse rs2) cs zs
                          in f6 [] qs cs zs2

f6 xs2@((l1,rs1):xs) qs2@((l2,rs2):qs) cs zs
        |l1<l2=let rs3=f7 rs1
                   cs3=f8 rs3 cs
               in f6 xs qs2 cs3 zs
        |otherwise=let  zs2=f9 l2 0 (reverse rs2) cs zs
                   in f6 xs2 qs cs zs2

f7 :: [Int]->[(Int,Int)]
f7 []=[]
f7 xs=let ys=group $ reverse xs
      in zip (map (head) ys) (map (length) ys) 

f8 :: [(Int,Int)]->[(Int,Int)]->[(Int,Int)]
f8 _ []=[]
f8 [] cs=cs
f8 rs2@((r1,c1):rs) cs2@((p2,c2):cs)
     |p2<r1=(p2,c2):f8 rs2 cs
     |p2>r1=f8 rs cs2
     |p2==r1=(p2,c2-c1):f8 rs cs

f9 :: Int->Int-> [Int]->[(Int,Int)]->[((Int,Int),Int)]->[((Int,Int),Int)]
f9 _ _ [] _ zs=zs
f9 _ _ _ [] zs=zs
f9 l1 c1 qs2@(q2:qs) ((p3,c3):all3) zs
        |q2>p3=f9 l1 (c1+c3) qs2 all3 zs
        |q2==p3=((l1,q2),c1+c3):f9 l1 (c1+c3) qs all3 zs
        
f10::Int->(Int,Int)->Bool
f10 n (a,b)=a<n

f11::[(Int,Int)]->Map.Map Int [Int]->Map.Map Int [Int]
f11 [] ms=ms
f11 ((l,r):xs) ms=f11 xs $ Map.insertWith (++) l (r:[]) ms

f12::(Int,Int)->(Int,Int)
f12 (a,b)
   |a<b=(a,b)
   |otherwise=(b,a)

main = do
       a<-getLine
       let (n:m:q:[])=(map read .words) a::[Int]
       xs1<-replicateM m (map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine)
       qs1<-replicateM q (map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine)
       --let gen1 = mkStdGen 8
       --    gen2 = mkStdGen 13
       --    gen3 = mkStdGen 11
       --    gen4 = mkStdGen 7
       --    xs2=map f12 $ take 100000 $ zip (randomRs (1,500) gen1) (randomRs (1,500) gen2)
       --    qs2=map f12 $ take 200000 $ zip (randomRs (1,500) gen3) (randomRs (1,500) gen4)
       --let qs2=f qs
       let xs3=sort $ f xs1
           qs2=f qs1
           --xs3=Arr.toList $ Arr.sort $ Arr.fromList $ f xs
           --xs3=sort $ xs2
           --xs3=H.toList $ H.fromList xs2
           --xs3=Arr.elems $ sort $ Arr.array $ zip [1..] xs2
           qs3=Set.toList $ Set.fromList $ qs2
           qs4=reverse $ f5 1 qs3 []
           xs4=reverse $ f5 1 xs3 []
           --xs4=tail $ Map.toList $ f11 xs3 (Map.fromList [(0,[0::Int])])
           --qs4=tail $ Map.toList $ f11 qs3 (Map.fromList [(0,[0::Int])])
           ms1=Map.fromList $ zip ([1..n]) (repeat 0::[Int])
           ys3=group $ sort $map (\(x,y)->y) xs3
           --ys3=group $ Arr.toList $ Arr.sort $ Arr.fromList $ map (\(x,y)->y) xs3
           ms2=Map.fromList $ zip (map (head) ys3) (map (length) ys3)
           ms4=Map.union ms2 ms1
           cs4=Map.toList ms4
           ans1=f6 xs4 qs4 cs4 []
           ans2=Map.fromList ans1
      　--print $ Map.size ans2
      　mapM_ putStrLn $ f4 qs2 ans2

Measured memory_bytes: 128380