Problem
Kazuma viaja com três companheiros: Aqua, Megumin e Darkness. Mas a viagem não é paga, então nosso esquadrão deve cumprir as tarefas atribuídas pela Guilda dos Aventureiros.
Kazuma já escolheu n tarefas para concluir. Porém, sempre que um esquadrão com força total assume algo, imprevistos e absurdos acontecem. É por isso que Kazuma decidiu que para cada uma das tarefas ele levaria
exatamente dois companheiros.
A proporção de cada um dos companheiros para Kazuma é caracterizada por um número inteiro. Inicialmente, a atitude de cada um deles é neutra e igual a 0. No processo de conclusão da tarefa, a atitude das meninas que ele assumiu a tarefa em relação a ele muda em uma direção positiva ou negativa (ou pode não mudar) .
Para cada uma das tarefas, Kazuma sabe como a atitude de cada garota em relação a ele mudará após a conclusão da tarefa. Ele quer levar companheiros nas tarefas para que, depois de cumprir todas elas, as atitudes de todas as meninas em relação a ele sejam iguais. Se isso pode ser alcançado de diferentes maneiras, é claro que é necessário que o relacionamento seja o melhor possível.
Ajude Kazuma a descobrir qual o tratamento mais igualitário que ele pode conseguir para todas as garotas.
Entrada:
A primeira linha contém um inteiro positivo n (1 ≤ n ≤ 25) — o número de tarefas a serem concluídas.
As próximas n linhas contêm descrições de — i-ésima linha contém três números a
i, m
i, d
i — o quanto as atitudes de Aqua, Megumin ou Darkness em relação a Kazuma mudarão, respectivamente, se o herói os levar com ele para completar a i-ésima tarefa.
Todos os números na entrada são inteiros e não excedem 10
7 em valor absoluto.
Saída:
Se não houver solução, imprima "Impossível" na primeira linha.
Caso contrário, imprima a relação que todas as garotas terão com Kazuma e, ao mesmo tempo, imprima o máximo possível.
Exemplos:
| Entrada |
Saída |
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
| Impossível |