【XR-1】快乐肥宅

题目背景

小粉兔的机房里面有 $n$ 个快乐肥宅,但小粉兔自己并不是,他看着这些快乐肥宅,非常羡慕,于是他想研究一下这些快乐肥宅的体重。

题目描述

每个快乐肥宅第 $0$ 天的体重都等于 $1$。第 $i$ 个快乐肥宅的体重记作 $w_i$,则一开始 $w_i = 1$。 第 $i$ 个快乐肥宅有一个专属的快乐指数 $k_i$,这表示他每天刚起床后,体重会是上一天的体重的 $k_i$ 倍。 肥宅们是有觉悟的,第 $i$ 个肥宅有一个专属的觉醒体重 $g_i$,这表示一旦他的体重**大于** $g_i$,他就会去健身房健身,每次减掉自己 $g_i$ 的体重,直到体重小于等于 $g_i$。 健身后,肥宅们会在机房见面,他们发现有时各自的体重会变得很有趣。 有一天,肥宅们发现各自的体重形成了等差数列! 另一天,肥宅们发现各自的体重形成了等比数列! 肥宅们心想,如果 $n$ 个快乐肥宅的体重 $\{w_1, w_2, \ldots, w_n\}$ 恰好形成序列 $\{r_1, r_2, \ldots, r_n\}$,至少需要经过多少天呢? 不过如果肥宅们等了很久都没有等到这一天,他们会认为这是不可能的。

输入输出格式

输入格式


第一行为一个正整数 $n$。 接下来 $n$ 行,每行三个正整数 $k_i, g_i, r_i$。分别表示第 $i$ 个肥宅的快乐指数、觉醒体重和序列中的体重。

输出格式


如果在第 $10^9$ 天结束前已经形成给定的序列,则输出一个数,表示至少需要经过的天数。 如果在第 $10^9$ 天结束前没有形成给定的序列,则输出 `Impossible`。

输入输出样例

输入样例 #1

2
4 7 4
2 5 3

输出样例 #1

7

输入样例 #2

2
4 7 3
2 5 3

输出样例 #2

Impossible

输入样例 #3

2
4 7 1
2 5 1

输出样例 #3

0

输入样例 #4

3
14 60 44
6 50 6
1029 91287 87318

输出样例 #4

101

输入样例 #5

1
6 65536 65536

输出样例 #5

16

输入样例 #6

2
2 2 2
2 3 1

输出样例 #6

2

说明

【样例 $1$ 说明】 下表是两个肥宅在第 $0$ 天至第 $7$ 天时的体重变化表: | 天数 | 肥宅 $1$ 的体重 | 肥宅 $2$ 的体重 | 解释 | | :--: | :--: | :--: | :--: | | $0$ | $1$ | $1$ | 第 $0$ 天每个肥宅的体重都是 $1$ | | $1$ | $4$ | $2$ | 肥宅 $1$ 的体重是上一天的 $4$ 倍,肥宅 $2$ 的体重是上一天的 $2$ 倍 | | $2$ | $2$ | $4$ | 肥宅 $1$ 的体重是上一天的 $4$ 倍,为 $16$,他发现自己的体重超过了 $7$,于是去了两次健身房,把体重减少了 $2\times 7=14$ | | $3$ | $1$ | $3$ | 这一天肥宅 $1$ 和肥宅 $2$ 都去了一次健身房 | | $4$ | $4$ | $1$ | 肥宅 $2$ 去了一次健身房 | | $5$ | $2$ | $2$ | 肥宅 $1$ 去了两次健身房 | | $6$ | $1$ | $4$ | 肥宅 $1$ 去了一次健身房 | | $7$ | $4$ | $3$ | 肥宅 $2$ 去了一次健身房 | 可以看出在第 $7$ 天时肥宅的体重形成了序列 $\{4, 3\}$。 【数据规模与约定】 Subtask 1(20 points):$n \le 50$,$g_i \le 50$。 Subtask 2(20 points):$g_i$ 为质数。 Subtask 3(20 points):$g_i \le 10^3$。 Subtask 4(20 points):$r_i \in \{1, g_i\}$。 Subtask 5(20 points):无特殊限制。 对于 $100\%$ 的数据,$1 \le n \le 10^3$,$1 \le k_i, r_i \le g_i \le 10^7$。