题目描述
Background
In Pink Rabbit's computer room, there are $n$ happy fat people, but Pink Rabbit himself is not one of them. He looks at these happy fat people with envy and wants to study their weights.
Problem Description
Each happy fat person's weight on day $0$ is equal to $1$. The weight of the $i$-th happy fat person is denoted as $w_i$, initially $w_i = 1$.
The $i$-th happy fat person has a unique happiness index $k_i$, which means that every morning, his weight will be $k_i$ times the weight of the previous day.
The fat people are conscious, and the $i$-th fat person has a unique awakening weight $g_i$, which means that once his weight exceeds $g_i$, he will go to the gym and lose his weight by $g_i$ each time, until his weight is less than or equal to $g_i$.
After working out, the fat people meet in the computer room, and they find that sometimes their weights become interesting.
One day, the fat people found that their weights formed an arithmetic sequence!
Another day, the fat people found that their weights formed a geometric sequence!
The fat people wondered, if the weights of $n$ happy fat people $\{w_1, w_2, \ldots, w_n\}$ exactly form the sequence $\{r_1, r_2, \ldots, r_n\}$, at least how many days would it take?
However, if the fat people wait a long time and this day never comes, they would think it is impossible.
Input Format
The first line is a positive integer $n$.
The next $n$ lines, each containing three positive integers $k_i, g_i, r_i$. These represent the happiness index, awakening weight, and the weight in the sequence for the $i$-th fat person, respectively.
Output Format
If the given sequence is formed before the end of day $10^9$, output a number representing the minimum number of days required.
If the given sequence is not formed before the end of day $10^9$, output Impossible.
Sample Input and Output
Sample Input #1
2
4 7 4
2 5 3
Sample Output #1
7
Sample Input #2
2
4 7 3
2 5 3
Sample Output #2
Impossible
Sample Input #3
2
4 7 1
2 5 1
Sample Output #3
0
Sample Input #4
3
14 60 44
6 50 6
1029 91287 87318
Sample Output #4
101
Sample Input #5
1
6 65536 65536
Sample Output #5
16
Sample Input #6
2
2 2 2
2 3 1
Sample Output #6
2
Notes
Sample 1 Explanation
The table below shows the weight changes of the two fat people from day $0$ to day $7$:
| Day | Weight of Fat Person 1 | Weight of Fat Person 2 | Explanation |
|---|---|---|---|
| $0$ | $1$ | $1$ | On day $0$, each fat person's weight is $1$ |
| $1$ | $4$ | $2$ | Fat Person 1's weight is $4$ times the previous day, Fat Person 2's weight is $2$ times the previous day |
| $2$ | $2$ | $4$ | Fat Person 1's weight is $4$ times the previous day, becomes $16$, he goes to the gym twice, reducing his weight by $2 \times 7 = 14$ |
| $3$ | $1$ | $3$ | Both Fat Person 1 and Fat Person 2 go to the gym once |
| $4$ | $4$ | $1$ | Fat Person 2 goes to the gym once |
| $5$ | $2$ | $2$ | Fat Person 1 goes to the gym twice |
| $6$ | $1$ | $4$ | Fat Person 1 goes to the gym once |
| $7$ | $4$ | $3$ | Fat Person 2 goes to the gym once |
It can be seen that on day $7$, the weights of the fat people form the sequence $\{4, 3\}$.
Data Constraints
Subtask 1 (20 points): $n \le 50$, $g_i \le 50$.
Subtask 2 (20 points): $g_i$ is a prime number.
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 data, $1 \le n \le 10^3$, $1 \le k_i, r_i \le g_i \le 10^7$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分