월향 가설 (Large)

이 문제는 월향 가설 (Small)과 $p$ 및 입력의 범위만 다른 문제입니다.

월향의 아이돌 거북이는 제곱수의 합에 관심이 많다. 최근에는 어떤 양의 정수를 $0$을 포함한 두 개의 제곱수의 합으로 나타낼 수 있는지에 대해 탐구하기 시작했다.

이러한 성질을 가지는 양의 정수에 '월향 수'라는 이름을 붙인 거북이는 오랜 시간 동안 계산한 결과 월향 수가 아닌 수의 목록을 얻었다. 이는 작은 순서대로 $3, 6, 7, \cdots$과 같다. 목록을 오랫동안 바라보던 거북이는 이 세 수가 다음과 같이 $\operatorname{mod} 13$에서 동시에 월향 수가 된다는 사실을 알아냈다!

$$\begin{cases} 3\equiv 16=0^2+4^2\pmod{13 }\\ 6\equiv 32=4^2+4^2\pmod{13} \\ 7\equiv 72=6^2+6^2\pmod{13}\end{cases}$$

거북이는 이 결과를 확장해서 다음과 같은 '월향 가설'을 만들었다.

임의의 음이 아닌 정수 $a_1,\cdots,a_N$이 $\operatorname{mod} p$에서 동시에 월향 수가 되는 소수 $p$가 존재한다. (단, $p>a_1,\cdots,a_N$.)

당신은 거북이를 도와 월향 가설의 정당성을 검증하려고 한다. $a_1,\cdots,a_N$이 주어질 때 월향 가설을 만족하는 소수 $p$가 존재하는지 판정하고, 만약 존재한다면 그러한 소수를 구하여라. 단, 소수가 너무 크면 검증하기 힘들기 때문에 $p<10^{12}$를 만족하여야 한다.

첫째 줄에 양의 정수 $N$이 주어진다. $(1\le N\le10\,000)$

둘째 줄에 $N$개의 정수 $a_1,\cdots,a_N$이 공백으로 구분되어 주어진다. $(0\le a_i\le 10^9)$

만일 $a_1,\cdots,a_N$이 동시에 $\operatorname{mod}p$에서 월향 수가 되는, $10^{12}$ 미만의 소수 $p$가 존재하지 않는다면 -1을 출력한다.

그렇지 않다면 첫째 줄에 그러한 소수 $p$를 출력한 뒤, 둘째 줄부터 한 줄에 하나씩 두 개의 음이 아닌 정수 $x_i, y_i$를 공백으로 구분하여 출력한다. $x_i, y_i$는 $a_i\equiv x_i^2+y_i^2\pmod p$를 만족하여야 한다. $(0\le x_i, y_i<p)$

그러한 $x_i, y_i$가 여러 개일 수 있으나, 조건을 만족한다면 아무거나 출력하여도 정답으로 인정된다.