탑

페탸와 바샤는 같은 보드게임을 아주 좋아합니다. 규칙이 꽤 복잡해서 이 문제에서는 규칙을 전부 설명하지 않습니다.

지도에는 탑이 두 줄로 놓여 있습니다. 위쪽 줄의 일부 탑은 도로로 아래쪽 줄의 탑과 연결되어 있습니다. 게임이 시작될 때 각 플레이어는 탑을 정확히 하나씩 가집니다. 첫 번째 플레이어는 위쪽 줄의 탑을, 두 번째 플레이어는 아래쪽 줄의 탑을 가집니다. 각 플레이어의 목표는 모든 탑을 차지하는 것입니다.

각 탑에는 비용이 있습니다. 비용은 게임마다 무작위로 정해지므로 첫 번째 플레이어가 항상 이기지는 않습니다. 페탸와 바샤는 시작할 때 자기 탑이 도로로 연결되어 있으면 게임이 재미없어진다는 점을 알아챘습니다. 이 경우 한 플레이어가 상대의 탑을 바로 빼앗을 수 있어서 첫 번째 턴에 게임이 끝나기 때문입니다. 또한 첫 번째 턴에 각자가 가진 탑 비용의 합이 클수록 게임이 더 재미있다는 점도 알아챘습니다.

두 사람은 시작 위치를 직접 고르는 일에 지쳐서 도움을 요청했습니다. 위쪽 줄의 탑은 왼쪽에서 오른쪽으로 1번부터 번호를 붙입니다. 아래쪽 줄의 탑도 같은 방식으로 번호를 붙입니다. 각 도로는 서로 다른 두 탑을 직접 잇습니다. 어떤 두 도로도 교차하지 않습니다. 형식적으로는 위쪽 탑 $i$와 아래쪽 탑 $j$를 잇는 도로가 있을 때, $i > k$이고 $j < l$인 도로 $(k, l)$이나 $i < k$이고 $j > l$인 도로 $(k, l)$은 존재하지 않습니다. 도로로 직접 연결되지 않은 탑 쌍 중에서 비용의 합이 최대인 쌍을 찾아야 합니다.

첫 줄에는 세 정수 $n$, $m$, $k$ ($1 \le n, m \le 10^5$, $0 \le k \le 10^5$)가 주어집니다. 각각 위쪽 줄 탑의 개수, 아래쪽 줄 탑의 개수, 도로의 개수입니다. 다음 $k$개 줄에는 두 정수 $a$와 $b$ ($1 \le a \le n$, $1 \le b \le m$)가 주어지며, 위쪽 탑 $a$와 아래쪽 탑 $b$ 사이에 도로가 있다는 뜻입니다. 그다음 줄에는 비용 집합의 개수 $t$ ($1 \le t \le 100$)가 주어집니다. 각 집합은 네 정수 $a$, $b$, $c$, $d$ ($1 \le a, b, c, d \le 10^6$)로 표현됩니다. 위쪽 줄 첫 번째 탑의 비용은 $a$입니다. $i$번째 탑의 비용을 $c_i$라고 하면, $i+1$번째 탑의 비용은 $(c_i \times b + c) \bmod d$입니다. 위쪽 줄의 마지막 탑 다음은 아래쪽 줄의 첫 번째 탑입니다.

각 비용 집합마다 한 줄에 조건을 만족하는 위쪽 탑 번호와 아래쪽 탑 번호를 출력합니다. 그런 쌍이 없으면 -1을 출력합니다. 답이 여러 개면 그중 아무거나 출력해도 됩니다.