Problem
カズマは、アクア、めぐみん、ダクネスの3人の仲間と共に旅をする。しかし、旅費は支払われないので、私たちのチームは冒険者ギルドによって割り当てられたタスクを完了する必要があります.
カズマはすでに n 個のタスクを完了させることを選択しています。しかし、総力を挙げて何かに挑むと、不測の事態や理不尽なことが起こります。そのため、カズマはそれぞれのタスクに
ちょうど 2 人 の仲間を連れて行くことにしました。
各コンパニオンとカズマの比率は整数で表されます。最初は、それぞれの態度はニュートラルで0に等しいです。タスクを完了する過程で、彼がタスクを引き受けた女の子の彼に対する態度は、正または負の方向に変化します（またはまったく変化しない場合があります）。 .
各タスクについて、カズマは、タスクの完了後に各女の子の態度がどのように変化するかを知っています.彼は仲間を任務に連れて行きたいと思っているので、それらすべてを完了した後、彼に対するすべての女の子の態度は平等です。これがさまざまな方法で達成できる場合は、もちろん、関係が可能な限り良好である必要があります。
カズマがすべての女の子に与えることができる最も平等な待遇を見つけるのを手伝ってください。
入力:
最初の行には、正の整数 n (1 ≤ n ≤ 25) — が含まれています。完了するタスクの数。
次の n 行には — の説明が含まれています。 i 番目の行には、3 つの数値 a
i、 m
i、 d
i が含まれています —主人公が i 番目のタスクを完了するためにアクア、めぐみん、またはダークネスを連れて行く場合、カズマに対するアクア、めぐみん、またはダークネスの態度がそれぞれ変化する量.
入力の数値はすべて整数で、絶対値で 10
7 を超えないでください。
出力:
解決策がない場合は、最初の行に「不可能」と出力してください。
それ以外の場合は、すべての女の子がカズマに対して持つ関係を出力し、同時に可能な限り最大の関係を出力します。
例:
<本体>
| 入力 |
出力 |
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
| 不可能 |