You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小粉兔的机房里面有 $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。

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

提示

【样例 $1$ 说明】

下表是两个肥宅在第 $0$ 天至第 $7$ 天时的体重变化表：

天数	肥宅 $1$ 的体重	肥宅 $2$ 的体重	解释
$0$	$1$		第 $0$ 天每个肥宅的体重都是 $1$
$1$	$4$	$2$	肥宅 $1$ 的体重是上一天的 $4$ 倍，肥宅 $2$ 的体重是上一天的 $2$ 倍
$2$		$4$	肥宅 $1$ 的体重是上一天的 $4$ 倍，为 $16$，他发现自己的体重超过了 $7$，于是去了两次健身房，把体重减少了 $2\times 7=14$
$3$	$1$	$3$	这一天肥宅 $1$ 和肥宅 $2$ 都去了一次健身房
$4$		$1$	肥宅 $2$ 去了一次健身房
$5$	$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$。