There are n cabs in a city numbered from 1 to n. The city has a rule that only one cab can run in the city at a time. Cab picks up the customer and drops him to his destination. Then the cab gets ready to pick next customer. There are m customers in search of cab. First customer will get the taxi first. You have to find the nearest cab for each customer. If two cabs have same distance then the cab with lower number is preferred.

Your task is to find out minimum distant cab for each customer.

Input:

The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M, denoting the number of cabs and the number of customers.

The next N lines contain two space-separated integers x[i] and y[i], denoting the initial position of the ith cab.

Next line contains an integer M denoting number of customers.
The next M lines contain four space seperated integers sx[i], sy[i], dx[i], dy[i], denoting the current location and the destination of the ith customer.

Output:

Output the nearest cab number for each customer.

Constraints:

1<=t<=10

1<=n,m<=1000

-10^9<=x[i] , y[i] , sx[i] , sy[i] , dx[i] , dy[i]<=10^9

Example:
Input:

1

3 2

1 3

3 2

3 5

2 3 3 4

5 3 4 1

Output:

1

1

Explanation:

The distance of cab1 from customer1 = sqrt((1-2)^2 + (3-3)^2) = 1

The distance of cab2 from customer1 = sqrt(2)

The distance of cab3 from customer1 = sqrt(5)

So output for customer1 is 1

Now location of cab1 is (3,4)

The distance of cab1 from customer2 = sqrt((3-5)^2 + (4-3)^2) = sqrt(5)

The distance of cab2 from customer2 = sqrt(5)

The distance of cab3 from customer2 = sqrt(8)

So output for customer2 is 1

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import math\ndef dist(w,x,y,z):\n return math.hypot(y - w, z - x)\n\nt = int(input())\nwhile (t>0):\n t = t -1\n n, m = list(map(int,input().split()))\n a = []\n for i in range(0,n):\n  x,y = list(map(int,input().split()))\n  a.append([x,y])\n for j in range(0,m):\n  p,q,r,s = list(map(int,input().split()))\n  nearest = -1\n  distance = 10000000000\n  for i in range(0,n):\n   way = dist(a[i][0],a[i][1],p,q)\n   if way < distance:\n    distance = way\n    nearest = i\n  print(nearest + 1)\n  a[nearest][0] = r\n  a[nearest][1] = s\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13605