Perhaps many have heard that the World Biathlon Championship has finished. Although our hero Valera was not present at this spectacular event himself and only watched it on TV, it excited him so much that he decided to enroll in a biathlon section.

Of course, biathlon as any sport, proved very difficult in practice. It takes much time and effort. Workouts, workouts, and workouts, — that's what awaited Valera on his way to great achievements in biathlon.

As for the workouts, you all probably know that every professional biathlete should ski fast and shoot precisely at the shooting range. Only in this case you can hope to be successful, because running and shooting are the two main components of biathlon. Valera has been diligent in his ski trainings, which is why he runs really fast, however, his shooting accuracy is nothing to write home about.

On a biathlon base where Valera is preparing for the competition, there is a huge rifle range with n targets. Each target have shape of a circle, and the center of each circle is located on the Ox axis. At the last training session Valera made the total of m shots. To make monitoring of his own results easier for him, one rather well-known programmer (of course it is you) was commissioned to write a program that would reveal how many and which targets Valera hit. More specifically, for each target the program must print the number of the first successful shot (in the target), or "-1" if this was not hit. The target is considered hit if the shot is inside the circle or on its boundary. Valera is counting on you and perhaps, thanks to you he will one day win international competitions.

Input

The first line of the input file contains the integer n (1 ≤ n ≤ 104), which is the number of targets. The next n lines contain descriptions of the targets. Each target is a circle whose center is located on the Ox axis. Each circle is given by its coordinate of the center x ( - 2·104 ≤ x ≤ 2·104) and its radius r (1 ≤ r ≤ 1000). It is guaranteed that no two targets coincide, intersect or are nested into each other, but they can touch each other.

The next line contains integer m (1 ≤ m ≤ 2·105), which is the number of shots. Next m lines contain descriptions of the shots, which are points on the plane, given by their coordinates x and y ( - 2·104 ≤ x, y ≤ 2·104).

All the numbers in the input are integers. 

Targets and shots are numbered starting from one in the order of the input.

Output

Print on the first line a single number, the number of targets hit by Valera. Print on the second line for each of the targets the number of its first hit or "-1" (without quotes) if this number does not exist. Separate numbers with spaces.

Examples

Input

3
2 1
5 2
10 1
5
0 1
1 3
3 0
4 0
4 0


Output

2
3 3 -1 


Input

3
3 2
7 1
11 2
4
2 1
6 0
6 4
11 2


Output

3
1 2 4

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Implementation


Solutions:
def main():
	from array import array
	from bisect import bisect
	from sys import stdin
	input = stdin.readline
	O = -1
	n = int(input())
	xr = []
	for i in range(n):
		(xi, ri) = map(int, input().split())
		xr.append((xi, ri ** 2, i))
	xr.sort()
	cur = 1
	res1 = 0
	res2 = array('i', (O,)) * n
	for _2 in range(int(input())):
		(x2, y) = map(int, input().split())
		bs = bisect(xr, (x2,))
		for i in (bs, bs - 1):
			if i < n:
				(xi, ri2, ii) = xr[i]
				if res2[ii] == O and (xi - x2) ** 2 + y ** 2 <= ri2:
					res1 += 1
					res2[ii] = cur
		cur += 1
	print(res1)
	print(*res2)
main()


from sys import stdin
from bisect import bisect_left
from collections import OrderedDict

def check(c, r, x, y):
	if x ** 2 + y ** 2 - 2 * x * c + c ** 2 <= r ** 2:
		return True
	else:
		return False
n = int(stdin.readline().strip())
rdict = OrderedDict()
center = []
for _ in range(n):
	(c, r) = list(map(int, stdin.readline().split()))
	rdict[c] = r
	center.append(c)
center.sort()
ans = dict()
m = int(stdin.readline().strip())
for i in range(m):
	(x, y) = list(map(int, stdin.readline().split()))
	index = bisect_left(center, x)
	if index > 0 and index < len(center):
		if check(center[index], rdict[center[index]], x, y):
			if center[index] not in ans:
				ans[center[index]] = i + 1
		if check(center[index - 1], rdict[center[index - 1]], x, y):
			if center[index - 1] not in ans:
				ans[center[index - 1]] = i + 1
	elif index == 0:
		if check(center[index], rdict[center[index]], x, y):
			if center[index] not in ans:
				ans[center[index]] = i + 1
	elif index == len(center):
		if check(center[index - 1], rdict[center[index - 1]], x, y):
			if center[index - 1] not in ans:
				ans[center[index - 1]] = i + 1
print(len(ans))
for i in rdict:
	if i in ans:
		print(ans[i], end=' ')
	else:
		print(-1, end=' ')


import sys
from array import array
from math import hypot

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
n = int(input())
circle = sorted(((x - r, x, r, i) for (i, (x, r)) in enumerate((map(int, input().split()) for _ in range(n))))) + [(10 ** 9, 10 ** 9, 10 ** 9, 10 ** 9)]
m = int(input())
shoot = sorted((tuple(map(int, input().split())) + (i,) for i in range(1, m + 1))) + [(10 ** 9, 10 ** 9, 10 ** 9)]
(inf, eps) = (10 ** 9, 1e-09)
ans = [inf] * n
si = 0
for (j, (sx, x, r, i)) in zip(range(n), circle):
	while shoot[si][0] < sx:
		si += 1
	while sx <= shoot[si][0] <= x + r:
		if hypot(x - shoot[si][0], shoot[si][1]) - eps < r and ans[i] > shoot[si][2]:
			ans[i] = shoot[si][2]
		if shoot[si][1] == 0 and circle[j + 1][0] == shoot[si][0] and (ans[circle[j + 1][3]] > shoot[si][2]):
			ans[circle[j + 1][3]] = shoot[si][2]
		si += 1
cnt = n
for i in range(n):
	if ans[i] == inf:
		ans[i] = -1
		cnt -= 1
sys.stdout.buffer.write((str(cnt) + '\n' + ' '.join(map(str, ans))).encode('utf-8'))


from sys import stdin, stdout
n = int(stdin.readline())
challengers = []
for i in range(n):
	(a, b) = map(int, stdin.readline().split())
	challengers.append((a, b, i))
challengers.sort()
ans = [float('inf') for i in range(n)]
m = int(stdin.readline())
questions = []
for i in range(m):
	(x, y) = map(int, stdin.readline().split())
	(l, r) = (-1, n)
	while r - l > 1:
		m = (r + l) // 2
		if challengers[m][0] <= x:
			l = m
		else:
			r = m
	if l >= 0 and (challengers[l][0] - x) ** 2 + y ** 2 <= challengers[l][1] ** 2:
		ans[challengers[l][2]] = min(ans[challengers[l][2]], i + 1)
	if r < n and (challengers[r][0] - x) ** 2 + y ** 2 <= challengers[r][1] ** 2:
		ans[challengers[r][2]] = min(ans[challengers[r][2]], i + 1)
stdout.write(str(n - ans.count(float('inf'))) + '\n')
for i in range(n):
	if ans[i] == float('inf'):
		stdout.write('-1' + ' \n'[i == n - 1])
	else:
		stdout.write(str(ans[i]) + ' \n'[i == n - 1])


input = __import__('sys').stdin.readline
import math
n = int(input())
lis = []
for i in range(n):
	(a, b) = map(int, input().split())
	lis.append([a, b, i])
lis.sort()
m = int(input())
ans = [-1] * n
c = 0
for i in range(m):
	(a, b) = map(int, input().split())
	l = 0
	r = n - 1
	while l <= r:
		mid = l + (r - l) // 2
		if lis[mid][0] <= a:
			l = mid + 1
		else:
			r = mid - 1
	ral = 1000000000000000
	if l <= n - 1:
		ral = math.sqrt((a - lis[l][0]) ** 2 + b ** 2)
	rar = math.sqrt((a - lis[r][0]) ** 2 + b ** 2)
	if l < n and ral <= lis[l][1] and (ans[lis[l][2]] == -1):
		ans[lis[l][2]] = i + 1
		c += 1
	if r < n and rar <= lis[r][1] and (ans[lis[r][2]] == -1):
		ans[lis[r][2]] = i + 1
		c += 1
print(c)
print(*ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def inside(x, y, c):
	R = radius[c] ** 2
	X = (x - c) ** 2
	Y = y ** 2
	return X + Y <= R
centers = []
radius = {}
ID = {}
n = Int()
for _ in range(n):
	(c, r) = value()
	centers.append(c)
	ID[_] = c
	radius[c] = r
centers.sort()
m = Int()
shots = []
status = defaultdict(lambda : -1)
for _ in range(m):
	shots.append(value())
for i in range(1, m + 1):
	(x, y) = shots[i - 1]
	ind = bisect_left(centers, x)
	if ind < n and inside(x, y, centers[ind]) and (status[centers[ind]] == -1):
		status[centers[ind]] = i
	ind -= 1
	if ind >= 0 and inside(x, y, centers[ind]) and (status[centers[ind]] == -1):
		status[centers[ind]] = i
print(len(status))
for i in range(n):
	print(status[ID[i]], end=' ')


from sys import stdin

def read(line):
	return [int(c) for c in line.split()]
test = stdin.readlines()
n = int(test[0])
targets = []
for i in range(1, n + 1):
	targets.append(read(test[i]))
m = int(test[n + 1])
shots = []
for i in range(n + 2, n + 2 + m):
	shots.append(read(test[i]))
grid = [-1] * 80000
for (i, t) in enumerate(targets):
	(x, r) = t
	for k in range(x - r, x + r + 1):
		if grid[k + 40000] == -1:
			grid[k + 40000] = i
		else:
			grid[k + 40000] = [grid[k + 40000], i]
ans = [-1] * n
for (k, s) in enumerate(shots, 1):
	(x, y) = s
	t = grid[x + 40000]
	if t != -1 and type(t) == int:
		(xx, r) = targets[t]
		if (xx - x) * (xx - x) + y * y <= r * r and ans[t] == -1:
			ans[t] = k
	elif type(t) == list:
		(xx, r) = targets[t[0]]
		if (xx - x) * (xx - x) + y * y <= r * r and ans[t[0]] == -1:
			ans[t[0]] = k
		(xx, r) = targets[t[1]]
		if (xx - x) * (xx - x) + y * y <= r * r and ans[t[1]] == -1:
			ans[t[1]] = k
print(sum((1 for e in ans if e != -1)))
print(*ans)


import sys
import math
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(th, d, ordering):
	sys.stdout.write(str(th) + '\n')
	for target in ordering:
		if target in d:
			sys.stdout.write(str(d[target]) + ' ')
		else:
			sys.stdout.write(str(-1) + ' ')
	sys.stdout.write('\n')

def binSearch(t, x):
	l = 0
	r = len(t) - 1
	while l <= r:
		m = (l + r) // 2
		if t[m][0] >= x:
			r = m - 1
		else:
			l = m + 1
	return r

def distFrom(point, xPos):
	(x1, y1) = (xPos, 0)
	(x2, y2) = point
	return abs(x2 - x1) ** 2 + abs(y2 - y1) ** 2

def solve(t, s):
	d = dict()
	targetsHit = 0
	for (x, y, shotNum) in s:
		m = binSearch(t, x)
		l = None
		r = None
		if 0 <= m <= len(t) - 1:
			l = m
		if 0 <= m + 1 <= len(t) - 1:
			r = m + 1
		if l != None:
			(pos, rad) = t[l]
			df = distFrom((x, y), pos)
			if df <= rad ** 2:
				if pos not in d:
					d[pos] = shotNum
					targetsHit += 1
		if r != None:
			(pos, rad) = t[r]
			df = distFrom((x, y), pos)
			if df <= rad ** 2:
				if pos not in d:
					d[pos] = shotNum
					targetsHit += 1
	return (targetsHit, d)

def readinput():
	n = getInt()
	originalOrdering = []
	targets = []
	for _ in range(n):
		(pos, rad) = getInts()
		originalOrdering.append(pos)
		targets.append((pos, rad))
	targets.sort()
	s = getInt()
	shots = []
	for i in range(s):
		(x, y) = getInts()
		shots.append((x, y, i + 1))
	(targetsHit, d) = solve(targets, shots)
	printOutput(targetsHit, d, originalOrdering)
readinput()