시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 24 7 3 15.000%

문제

서기 2042년. 인터넷은 가상 현실을 만들 정도로 발전했고 사이버 범죄는 매일 일어난다. 그래서 2041년 SWERC 대회 우승자는 사이버 범죄가 일어날 때마다 도넛을 떨어뜨리는 요원을 개발해냈다. 모든 도넛은 고유 번호가 있고, 마드리드 경찰국은 범죄 정보와 그 범죄의 도넛 고유번호가 담긴 커다란 DB를 가지고 있다.

오늘은 너의 날이다. 너의 임무는 DB에 담긴 기록을 읽어 새로운 범죄 현장의 도넛과 유사한 도넛을 찾아내는 새로운 요원을 개발하는 것이다.

가상 범죄학 전문가들은 도넛 간의 유사성 판별의 기준을 제시했다. 그것은 도넛의 구멍의 반지름의 차와 도넛 전체의 반지름의 차의 합이다.

입력

모든 테스트 케이스는 첫 번째 줄에 DB 속의 도넛의 개수인 n이 주어진다. (1 ≤ n ≤ 100, 000)

그 뒤의 n개의 줄 중에서 i번째 줄은 i번째 도넛의 구멍의 반지름과 도넛 전체의 반지름을 나타내는 두 개의 정수 l과 w가 주어진다. (1 ≤ l, w ≤ 109)

그리고 나서는 당신이 DB에서 찾는 도넛의 개수를 나타내는 q가 주어진다. (1 ≤ q ≤ 50, 000)

그 뒤의 q개의 줄 중에서 i번째 줄은 i번째 도넛의 차원을 나타낸다.

다른 테스트 케이스는 빈 줄로 구분되며 입력의 종료 전에 -1이 주어진다.

출력

매 테스트 케이스의 출력물은 정수로 이루어진 q개의 줄이어야 한다. i번째 줄에는 새로 발견된 i번째 도넛과 가장 가까운 DB의 도넛 간의 유사도를 출력하라.

서로 다른 테스트 케이스에 대한 답안은 빈 줄로 구분되어야 한다.

예제 입력

2
2 3
3 4
2
1 1
3 4

2
1 1
9 9
4
4 5
6 5
2 5
3 4

-1

예제 출력

3
0

7
7
5
5

힌트