최소 곱

정수 배열 $a_1, a_2, \dots, a_n$이 주어진다. $i < j$이고 $a_i < a_j$이며 곱 $a_i \cdot a_j$가 가능한 한 작아지는 두 인덱스 $i$와 $j$를 찾아라.

입력은 여러 개의 테스트로 이루어진다. 첫째 줄에 테스트의 수 $t$가 주어진다 ($1 \leq t \leq 10^4$). 다음 $t$개의 줄에 각각 하나의 테스트가 주어진다.

각 테스트는 다음과 같은 알고리즘으로 생성된다. 테스트는 정수 $n$, $l$, $r$, $x$, $y$, $z$, $b_1$, $b_2$로 주어진다 ($2 \leq n \leq 10^7$, $-2\cdot10^9 \leq l \leq r \leq 2\cdot10^9$, $0 \leq x, y, z, b_1, b_2 < 2^{32}$). $n$은 배열의 길이이다.

먼저 길이 $n$인 수열 $b_i$를 생성한다. $b_1$과 $b_2$는 주어진다. $i > 2$인 경우 $b_i = (b_{i-2}x + b_{i-1}y + z) \bmod 2^{32}$이다. $1$부터 $n$까지의 각 $i$에 대해 $a_i = (b_i \bmod (r - l + 1)) + l$이다. 따라서 $-2\cdot10^9 \leq a_i \leq 2\cdot10^9$이다.

정수 오버플로를 피하려면 수열을 생성할 때 64비트 정수를 사용하는 것이 좋다.

모든 테스트에서 $n$의 합은 $2 \cdot 10^7$을 넘지 않는다.

각 테스트마다 가능한 가장 작은 곱 $a_i \cdot a_j$를 한 줄에 하나씩 출력한다. $i < j$이고 $a_i < a_j$인 $i$와 $j$가 존재하지 않으면 "IMPOSSIBLE"을 출력한다.

첫 번째 테스트에서 배열이 생성되는 과정을 살펴보자.

먼저 수열 $b$를 생성한다.

• $b_1 = 0$
• $b_2 = 3$
• $b_3 = (11\cdot 0 + 13\cdot 3 + 17) \bmod 2^{32} = 56$
• $b_4 = (11\cdot 3 + 13\cdot 56 + 17) \bmod 2^{32} = 778$

이어서 이 수열로 $a$를 생성한다.

• $a_1 = (0 \bmod (5 - (-5) + 1)) + (-5) = (0 \bmod 11) - 5 = -5$
• $a_2 = (3 \bmod 11) - 5 = -2$
• $a_3 = (56 \bmod 11) - 5 = -4$
• $a_4 = (778 \bmod 11) - 5 = 3$

따라서 $a = [-5, -2, -4, 3]$이다. 답은 $-5 \cdot 3 = -15$이다.

두 번째 테스트에서 배열은 $[42, 42, 42, 42, 42]$이다.