음식 배달 앱

배달 앱에 N개의 식당과 M명의 고객이 있다. 각 식당은 (x, y) 좌표에 위치하고 조리 시간이 있다. 각 고객도 (x, y) 좌표에 위치한다. 배달 시간 = 맨해튼 거리 + 조리 시간이다. 각 고객에게 배달 시간이 가장 짧은 식당의 번호를 출력하시오. 동점이면 번호가 작은 식당을 선택한다.

입력

첫째 줄에 식당 수 N이 주어진다. 다음 N줄에 식당 좌표 (xi yi)와 조리 시간 ci가 주어진다. 다음 줄에 고객 수 M이 주어진다. 다음 M줄에 고객 좌표 (xj yj)가 주어진다.

• 1 ≤ N, M ≤ 100,000
• 0 ≤ 좌표 ≤ 10,000
• 0 ≤ 조리 시간 ≤ 10,000

출력

M줄에 걸쳐 각 고객에게 가장 빠른 식당 번호(1-indexed)를 출력한다.

예제 입력

2
0 0 5
10 0 2
2
5 0
8 0

예제 출력

1
2