Problem
Kazuma 与三个伙伴一起旅行:Aqua、Megumin 和 Darkness。但是旅费是没有报酬的,所以我们小队必须完成冒险者公会布置的任务。
Kazuma 已经选择了 n 个要完成的任务。然而,每当一支全副武装的小队承担某事时,就会发生无法预料和荒谬的事情。这就是为什么 Kazuma 决定在每个任务中他都会带
正好两个同伴。
每个同伴与 Kazuma 的比率以整数为特征。最初,他们每个人的态度都是中立的,等于0。在完成任务的过程中,他所接任务的女孩对他的态度发生了正向或负向的变化(也可能根本没有变化) .
对于每一个任务,和真都知道每个女孩在完成任务后对他的态度会有怎样的变化。他要带同伴去完成任务,完成所有任务后,所有女孩对他的态度都是平等的。如果这可以通过不同的方式实现,那么,当然,关系要尽可能好。
帮助 Kazuma 弄清楚他能为所有女孩提供最平等的待遇。
输入:
第一行包含一个正整数 n (1 ≤ n ≤ 25) —要完成的任务数。
接下来的 n 行包含对 — 的描述。第 i 行包含三个数字 a
i, m
i, d
i —如果英雄带他们一起完成第 i 个任务,阿克娅、惠惠或达克尼斯对和真的态度将分别改变多少。
输入的所有数字都是整数,绝对值不超过10
7。
输出:
如果无解,则在第一行打印“Impossible”。
否则,打印出所有女生对和真的关系,同时打印出最大可能。
示例:
<正文>
输入 |
输出 |
3
1 0 0
0 1 0
0 0 1
| 1 |
7
0 8 9
5 9 -2
6-8-7
9 4 5
-4 -9 9
-4 5 2
-6 8 -7
| 5 |
2
1 0 0
1 1 0
| 不可能 |
表>