13145번 - Masonry Bridge

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

다현이와 정연이는 배를 타고 서로의 섬을 드나드는 것이 불편해서 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)

두 번째 줄부터 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개이다.

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