고속도로 연결

바이트랜드에는 Red와 Blue 두 회사가 운영하는 고속도로망이 있다. 두 망은 모두 교차점과, 교차점 두 개를 잇는 직선 구간으로 이루어진다. 한 망 안에서 두 구간은 교차점에서만 맞닿고 다른 점에서는 만나지 않는다. 두 망은 각각 연결되어 있어서 같은 망의 교차점 두 개는 언제나 구간을 따라 오갈 수 있다. 한 교차점이 두 망에 동시에 속하는 일은 없다. 서로 다른 망에 속한 구간끼리는 교차해도 된다.

두 회사가 합병하기로 했다. Red의 교차점 하나와 Blue의 교차점 하나를 잇는 직선 구간을 하나만 새로 지어서 두 망을 연결하려고 한다. 새 구간은 자기 두 끝점을 빼면 기존 구간과 어떤 점도 공유하면 안 된다.

입력은 Red 망의 정보와 Blue 망의 정보를 차례로 담는다. 각 망의 첫 줄에는 교차점의 개수 $N$과 구간의 개수 $M$이 주어진다 ($2 \le N \le 200000$, $1 \le M \le 700000$). 다음 $N$개 줄에는 교차점의 좌표 $x$와 $y$가 주어진다 ($-1000000 \le x, y \le 1000000$). 교차점의 번호는 입력에 나온 순서대로 $1$부터 $N$까지다. 그다음 $M$개 줄에는 구간의 양 끝 교차점 번호 $p$와 $q$가 주어진다 ($1 \le p, q \le N$, $p \ne q$).

어떤 교차점도 다른 망의 구간 위에 놓이지 않는다.

새로 짓는 구간의 두 끝점 $u$와 $v$를 출력한다. $u$는 Red 망의 교차점 번호, $v$는 Blue 망의 교차점 번호이고, 두 점을 잇는 구간은 $u$와 $v$를 빼면 어느 망의 구간과도 만나지 않는다.

조건을 만족하는 쌍은 여러 개일 수 있으므로 답은 다음 규칙으로 하나만 정한다.

점 $P$가 점 $Q$보다 높다는 것은 $P$의 $y$좌표가 더 크거나, $y$좌표가 같고 $x$좌표가 더 크다는 뜻이다. 두 망의 모든 교차점 가운데 가장 높은 점을 $t$라 하고, $t$가 속하지 않은 망에서 가장 높은 교차점을 $b$라 하자. $t$가 속한 망의 교차점 $a$ 가운데 $b$보다 높으면서 위 조건대로 $b$와 이을 수 있는 점만 생각한다. 그런 $a$는 항상 존재한다. 이 가운데 $b$에서 $a$로 향하는 벡터가 $x$축 양의 방향과 이루는 반시계 방향 각이 가장 작은 점을 고른다. 이 각은 항상 $0$도 이상 $180$도 미만이다. 각이 같은 점이 둘 이상이면 $b$에 더 가까운 점을 고른다. 이렇게 정해진 쌍에서 Red 망의 번호를 먼저, Blue 망의 번호를 나중에 출력한다.

그림은 예제의 두 망과, 규칙이 고르는 연결 구간을 점선으로 보여준다.