Description

Each happy chubby guy’s weight on day $0$ is $1$. Let the $i$-th happy chubby guy’s weight be $w_i$, so initially $w_i = 1$.

The $i$-th happy chubby guy has a personal happiness index $k_i$, meaning that every day right after he wakes up, his weight becomes $k_i$ times his weight from the previous day.

These chubby guys are determined. The $i$-th chubby guy has a personal awakening weight $g_i$, meaning that once his weight is greater than $g_i$, he will go to the gym. Each time, he reduces his weight by $g_i$, until his weight is less than or equal to $g_i$.

After working out, they meet in the computer lab, and they find that sometimes their weights become very interesting.

One day, they found that their weights formed an arithmetic progression.

Another day, they found that their weights formed a geometric progression!

The chubby guys wonder: if the weights of the $n$ happy chubby guys $\{w_1, w_2, \ldots, w_n\}$ exactly form the sequence $\{r_1, r_2, \ldots, r_n\}$, what is the minimum number of days needed?

However, if they wait for a very long time and still do not reach that day, they will think it is impossible.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain three positive integers $k_i, g_i, r_i$, representing the $i$-th chubby guy’s happiness index, awakening weight, and the target weight in the sequence.

Output Format

If the given sequence is formed before the end of day $10^9$, output one number: the minimum number of days required.

If the given sequence is not formed before the end of day $10^9$, output Impossible.

2
4 7 4
2 5 3

7

2
4 7 3
2 5 3

Impossible

2
4 7 1
2 5 1

0

3
14 60 44
6 50 6
1029 91287 87318

101

1
6 65536 65536

16

2
2 2 2
2 3 1

2

Hint

[Sample $1$ Explanation]

The table below shows the weight changes of two chubby guys from day $0$ to day $7$:

It can be seen that on day $7$, the chubby guys’ weights form the sequence $\{4, 3\}$.

[Constraints and Notes]

Subtask 1 (20 points): $n \le 50$, $g_i \le 50$.
Subtask 2 (20 points): $g_i$ is prime.
Subtask 3 (20 points): $g_i \le 10^3$.
Subtask 4 (20 points): $r_i \in \{1, g_i\}$.
Subtask 5 (20 points): no special constraints.

For $100\%$ of the testdata: $1 \le n \le 10^3$, $1 \le k_i, r_i \le g_i \le 10^7$.

Translated by ChatGPT 5