import qualified Data.ByteString.Char8  as C
import Data.List
import Data.Ord

main = sol <$> get >>= put
get = fmap (unfoldr (C.readInt . C.dropWhile (==' '))) . C.lines <$> C.getContents
put = mapM_ print

sol ([n,m]:xys) = fmap f ab
  where
  (ab,cd) = splitAt n xys
  cs = zip cd [1..]
  f [x,y] = snd $ minimumBy (comparing (dist [x,y]) `mappend` compare) cs
  dist [x,y] ([x',y'],_) = abs (x-x') + abs (y-y')
