Kazuma travels with three companions: Aqua, Megumin, and Darkness. But travel is not paid, so our squad must complete the tasks assigned by the Adventurer's Guild.
Kazuma has already chosen n tasks to complete. However, whenever a squad in full force takes on something, unforeseen and absurd things happen. That is why Kazuma decided that for each of the tasks he would take
exactly two companions.
The ratio of each of the companions to Kazuma is characterized by an integer. Initially, the attitude of each of them is neutral and equal to 0. In the process of completing the task, the attitude of the girls he took on the task towards him changes in a positive or negative direction (or may not change at all).
For each of the tasks, Kazuma knows how each girl's attitude towards him will change after completing the task. He wants to take companions on assignments so that after completing all of them, the attitudes of all the girls towards him are equal. If this can be achieved in different ways, then, of course, it is necessary that the relationship be as good as possible.
Help Kazuma figure out what the most equal treatment he can get for all the girls.
Input:
The first line contains a positive integer n (1 ≤ n ≤ 25) — the number of tasks to complete.
The next n lines contain descriptions of — i-th line contains three numbers a
i, m
i, d
i — the amount by which Aqua, Megumin or Darkness's attitudes towards Kazuma will change, respectively, if the hero takes them with him to complete the i-th task.
All numbers in the input are integers and do not exceed 10
7 in absolute value.
Output:
If there is no solution, print "Impossible" in the first line.
Otherwise, print the relationship that all girls will have towards Kazuma, and at the same time, print the maximum possible.
Examples:
| Input |
Output |
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
| Impossible |