다현이와 정연이는 N개의 섬이 있는 ‘여울 마을’에서 살고 있다. 다현이는 가장 동쪽에 있는 섬에서 살고 있으며 정연이는 가장 서쪽에 있는 섬에서 살고 있다. 다현이와 정연이는 ‘여울 마을’의 N개의 섬에 1~N의 고유 번호를 붙였는데, 정연이가 살고 있는 섬을 1번으로, 다현이가 살고 있는 섬을 N번으로 붙였다.</p>

다현이와 정연이는 배를 타고 서로의 섬을 드나드는 것이 불편해서 3번 섬에서 살고 있는 건축가 성열이를 불러서 N개의 섬을 연결하는 돌다리를 건설해달라고 부탁했다.

성열이는 우선 N개의 섬을 잇는 돌다리를 어떻게 지을 지 계획했다. 그 결과 성열이는 총 M개의 돌다리를 짓기로 생각했다. 성열이가 M개의 돌다리를 지은 후에는 N개의 섬들이 모두 연결되며, M개의 돌다리들은 중간에서 겹치지 않으며 양 끝의 두 섬을 제외한 다른 섬을 지나지 않는다. 각 돌다리는 짓는 데 T_k의 시간이 걸린다.

성열이는 M개의 돌다리를 무작위 순서로 지을 것이다. 성열이가 돌다리를 짓다 보면 다현이와 정연이가 서로의 섬을 돌다리를 이용해서 건널 수 있는 순간이 올 것이다.

위 그림과 같은 형태의 섬을 생각해보자. 만약 성열이가 9개의 돌다리를 번호 순서(1, 2, …, 9)대로 짓는다면, 총 6개의 돌다리를 지은 후의 상태인 17 단위 시간 후에 1번 섬과 N번 섬이 연결된다. 한편, 성열이가 1번 돌다리를 짓고 6번 돌다리를 짓는다면 6 단위 시간 후에 1번 섬과 N번 섬이 연결된다. 성열이가 다리를 어떤 순서대로 건설해도 5 단위 시간 후에 1번 섬에서 N번 섬까지 갈 수 없다.

또, 성열이가 1, 9, 7, 5, 8, 3, 2, 6, 4번 돌다리를 순서대로 짓는다면 총 6개의 돌다리를 지은 후의 상태인 22 단위 시간 후에 1번 섬과 N번 섬이 연결된다. 성열이가 다리를 어떤 순서대로 건설해도 22 단위 시간 후에는 항상 1번 섬에서 N번 섬까지 갈 수 있다.

다현이와 정연이는 서로의 섬을 돌다리를 이용해서 드나들 수 있는 시점이 언제인지 궁금하다. 섬과 돌다리의 정보가 주어질 때, 1번 섬과 N번 섬이 연결되는 시점의 최솟값과 최댓값을 구하는 프로그램을 작성하여라.

입력 형식

첫 번째 줄에는 섬의 수 N이 주어진다. (4 ≤ N ≤ 50,000)</p>

두 번째 줄부터 N개의 줄에는 각 섬의 좌표 X_k, Y_k가 주어진다. (1 ≤ X_k, Y_k ≤ 1,000,000, X₁ < X_k < X_N)

N+2번째 줄에는 성열이가 지으려고 계획한 돌다리의 수 M이 주어진다. (N-1 ≤ M ≤ 1,000,000)

그 다음 줄부터 M개의 줄에는 성열이가 지으려는 k번째 돌다리가 연결하는 두 섬의 번호 S_k, E_k와 건설시간 T_k가 주어진다. (S_k ≠ E_k, 1 ≤ T_k ≤ 10,000)

1번 섬과 x좌표가 똑같거나 1번 섬보다 x좌표가 작은 섬이 없다. 또, N번 섬과 x좌표가 똑같거나 N번 섬보다 x좌표가 큰 섬도 없다. 위치가 완전히 겹치는 두 섬도 없다. 또한, 임의의 두 섬에 대해서 그 두 섬을 연결하는 돌다리는 최대 1개이다.

출력 형식

다현이와 정연이가 서로의 섬을 돌다리를 이용해서 건널 수 있는 시점의 최솟값과 최댓값을 출력한다.

예제 입력

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

예제 출력

6 22