Minimal Product

You are given an array of integers $a_1, a_2, \dots, a_n$. Find two indices $i$ and $j$ such that $i < j$, $a_i < a_j$, and the product $a_i \cdot a_j$ is as small as possible.

The input consists of several tests. The first line contains a single integer $t$, the number of tests ($1 \leq t \leq 10^4$). Each of the following $t$ lines describes one test.

Each test is generated using the following algorithm. The test is described by integers $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}$), where $n$ is the length of the array.

First, the sequence $b_i$ of length $n$ is generated. The elements $b_1$ and $b_2$ are given. For $i > 2$, let $b_i = (b_{i-2}x + b_{i-1}y + z) \bmod 2^{32}$. For each $i$ between $1$ and $n$, $a_i = (b_i \bmod (r - l + 1)) + l$ (thus, $-2\cdot10^9 \leq a_i \leq 2\cdot10^9$).

Use 64-bit integers to generate the sequence and avoid integer overflow.

The sum of $n$ over all tests does not exceed $2 \cdot 10^7$.

For each test, print the smallest possible product $a_i \cdot a_j$ on a separate line. If there are no indices $i$ and $j$ such that $i < j$ and $a_i < a_j$, print "IMPOSSIBLE".

Consider how the array is generated in the first test.

First, the sequence $b$ is generated.

• $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$

Then it is used to generate $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$

Thus, $a = [-5, -2, -4, 3]$. The answer is $-5 \cdot 3 = -15$.

In the second test the array is $[42, 42, 42, 42, 42]$.