거의 항상

오늘 확률론 수업에서는 높은 확률로 일어나는 확률적 사건을 다루었다. 친구에게 설명하듯이 말하자면, 어떤 매개변수 $n$이 무한대로 갈 때 이 사건의 확률이 $1$로 간다는 뜻이다.

높은 확률로 일어나는 사건의 예로는 다음이 있다. $1$과 $2\cdot 10^9$ 사이의 독립적인 균등 랜덤 정수 $n$개가 주어졌을 때, 한 원소가 다른 원소를 나누는 두 원소가 존재한다.

친구는 이것을 믿지 않는다. 어느 수도 다른 수를 나누지 않는 예를 쉽게 많이 만들 수 있기 때문이다. $\{10^9+1, 10^{9}+2, \dots, 2\cdot 10^9\}$의 임의의 부분집합을 잡으면, 그중 어느 수도 다른 수를 나누지 않는다!

친구를 설득하기 위해, 정확히 $100$개의 문제 인스턴스에 대해 서로를 나누는 두 원소를 찾을 수 있음을 보여 주려 한다. $n=5\cdot 10^5$일 때 인스턴스당 실패 확률이 $10^{-25}$보다 작으므로 성공할 것이라 확신한다.

입력은 다음과 같다.

• 정수 $n$ 하나가 주어지는 한 줄. 이는 리스트에 있는 정수의 개수이다.
• $\{1, 2, \ldots, 2\cdot 10^9\}$에서 균등하게 뽑은 $n$개의 독립적인 랜덤 정수 $a_1, \ldots, a_n$이 주어지는 한 줄.

제출한 코드는 정확히 $100$개의 테스트 케이스에 대해 실행되며, 모두 $n=5\cdot 10^5$이다. 예제는 더 작으며 설명을 위한 것이다.

각 제출은 새로운 랜덤 테스트 케이스에 대해 실행된다.

$a_{i}$가 $a_{j}$를 나눈다는 것을 나타내는 서로 다른 두 정수 $i$와 $j$를 출력한다.