약수 게임

Bajtuś와 Bituś가 새로운 게임을 합니다. 처음에 칠판에는 $N > 1$인 정수 $N$이 하나 적혀 있습니다. 두 사람은 번갈아 가며 자기 차례에 현재 칠판에 적힌 수를 그 수 자신과는 다른 약수 중 하나로 바꿉니다. 누군가 수 $1$을 적는 순간 게임이 끝납니다.

$N$ 자신을 제외한 $N$의 모든 약수 $d$에 대해 두 값 $a(d)$와 $b(d)$가 미리 주어집니다. Bajtuś가 $d$를 적으면 $a(d)$점을 얻고, Bituś가 $d$를 적으면 $b(d)$점을 얻습니다. 두 사람은 모두 자신의 이득, 즉 자신의 총점에서 상대의 총점을 뺀 값을 최대화하려고 합니다.

Bituś는 이미 $N$과 모든 점수를 정해 두었고, 누가 먼저 시작할지는 Bajtuś가 고를 수 있습니다. 두 사람이 모두 최적으로 플레이한다고 할 때, Bajtuś가 먼저 시작하는 경우와 Bituś가 먼저 시작하는 경우 각각에 대해 시작한 사람의 이득을 구하세요.

첫 줄에는 테스트 케이스의 개수인 양의 정수 $t$가 주어집니다. 이어서 각 테스트 케이스가 차례대로 주어집니다.

각 테스트 케이스의 첫 줄에는 네 정수 $n_1$, $n_2$, $n_3$, $D$가 주어집니다 ($1 \le n_i \le 5 \cdot 10^6$, $1 < n_1 n_2 n_3 \le 8 \cdot 10^{18}$). 이들의 곱 $N = n_1 \cdot n_2 \cdot n_3$이 처음에 칠판에 적힌 수이며, $D$는 $N$의 양의 약수 개수입니다.

다음 $D - 1$개 줄에는 $N$ 자신을 제외한 $N$의 약수들의 점수가 약수 값이 커지는 순서로 주어집니다. 이 중 $i$번째 줄에는 두 정수 $a(d)$와 $b(d)$가 있으며 ($-10^9 \le a(d), b(d) \le 10^9$), 이는 $N$의 $i$번째로 작은 약수 $d$를 적을 때 Bajtuś와 Bituś가 각각 얻는 점수입니다.

모든 테스트 케이스에 걸친 $D$의 합은 $10^6$을 넘지 않습니다.

각 테스트 케이스마다 두 정수 $A$와 $B$를 한 줄에 출력하세요. $A$는 Bajtuś가 먼저 시작할 때 시작한 사람의 이득이고, $B$는 Bituś가 먼저 시작할 때 시작한 사람의 이득이며, 둘 다 두 사람이 최적으로 플레이한 결과입니다.

첫 번째 예제에서는 $N = 7$이 소수이므로 시작한 사람은 $1$만 적을 수 있고, 그 즉시 게임이 끝나며 $1$에 부여된 점수를 받습니다. 두 번째 예제에서는 $N = 4$이며, 차례인 사람은 $2$를 적고 상대가 $1$을 적도록 만드는 편이 이득입니다.