34809번 - 월향 가설 (Small) 스페셜 저지

문제

이 문제는 월향 가설 (Large)와 $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^8$을 만족하여야 한다.

입력

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

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

출력

만일 $a_1,\cdots,a_N$이 동시에 $\operatorname{mod}p$에서 월향 수가 되는 10ドル^8$ 미만의 소수 $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$가 여러 개일 수 있으나, 조건을 만족한다면 아무거나 출력하여도 정답으로 인정된다.

제한

노트