좋은 카트 만들기

루시드는 $N$ 종류의 카트 엔진과 $M$ 종류의 카트 핸들을 가지고 있다. 편의상 카트 엔진의 각 종류는 $1$부터 $N$까지 번호가 매겨져 있으며, 카트 핸들의 각 종류는 $1$부터 $M$까지 번호가 매겨져 있다. $i$ 번 종류의 카트 엔진의 성능은 $A_i$, 무게는 $B_i$이고, $j$ 번 종류의 카트 핸들의 성능은 $C_j$, 무게는 $D_j$이다.

한 종류의 카트 엔진과 한 종류의 카트 핸들을 선택하여 조합하면, 하나의 카트가 완성된다. 이렇게 만들어진 카트의 점수는 카트 엔진과 카트 핸들의 성능 합을 무게 합으로 나눈 것이 된다.

즉, $i$ 번 종류의 카트 엔진과 $j$ 번 종류의 카트 핸들을 선택하여 조합해 만들어진 카트의 점수는 다음과 같다:

루시드를 도와 각 카트 엔진마다 어느 카트 핸들과 조합해야 점수가 가장 높은 카트를 만들 수 있는지 구하는 프로그램을 작성하라.

입력 형식

첫 줄에 카트 엔진의 종류 수를 나타내는 정수 $N$과 카트 핸들의 종류 수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 300\,000)$

다음 $N$ 개의 줄에 걸쳐 카트 엔진의 성능을 나타내는 정수 $A_i$와 카트 엔진의 무게를 나타내는 정수 $B_i$가 공백으로 구분되어 주어진다. $(1 \le A_i, B_i, \le 1\,000\,000\,000)$

다음 $M$ 개의 줄에 걸쳐 카트 핸들의 성능을 나타내는 정수 $C_j$와 카트 핸들의 무게를 나타내는 정수 $D_j$가 공백으로 구분되어 주어진다. $(1 \le C_j, D_j \le 1\,000\,000\,000)$

출력 형식

$N$ 개의 줄에 걸쳐 각 카트 엔진마다 어느 카트 핸들과 조합해야 점수가 가장 높은 카트를 만들 수 있는지 출력한다.

$i$ 번째 줄에 $i$ 번 종류의 카트 엔진과 조합했을 때 가장 높은 점수의 카트를 만들 수 있는 카트 핸들의 종류 번호를 출력한다. 만약, 가능한 답이 여러 가지인 경우 카트 핸들의 종류 번호가 가장 작은 것을 출력한다.

예제

4 5
5 2
6 3
7 5
10 8
2 1
4 2
3 3
7 4
8 5

1
1
2
4

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설