P5345 [XR-1] Happy Chubby Guys

There are $n$ happy chubby guys in Xiaofentu’s computer lab, but Xiaofentu is not one of them. He looks at these happy chubby guys and feels very jealous, so he wants to study their weights.

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.

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.

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`.

[Sample $1$ Explanation] The table below shows the weight changes of two chubby guys from day $0$ to day $7$: | Days | Chubby guy $1$’s weight | Chubby guy $2$’s weight | Explanation | | :--: | :--: | :--: | :--: | | $0$ | $1$ | $1$ | On day $0$, each chubby guy’s weight is $1$ | | $1$ | $4$ | $2$ | Chubby guy $1$’s weight is $4$ times the previous day, and chubby guy $2$’s weight is $2$ times the previous day | | $2$ | $2$ | $4$ | Chubby guy $1$’s weight is $4$ times the previous day, which is $16$. He finds his weight exceeds $7$, so he goes to the gym twice, reducing his weight by $2\times 7=14$ | | $3$ | $1$ | $3$ | On this day, both chubby guy $1$ and chubby guy $2$ go to the gym once | | $4$ | $4$ | $1$ | Chubby guy $2$ goes to the gym once | | $5$ | $2$ | $2$ | Chubby guy $1$ goes to the gym twice | | $6$ | $1$ | $4$ | Chubby guy $1$ goes to the gym once | | $7$ | $4$ | $3$ | Chubby guy $2$ goes to the gym once | 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