URI Online Judge | 3278

Passageiros de Trem

Por Michał Pilipczuk and Marc Vinyals NO Norway

Timelimit: 1

A Nordic Company of Passing Carriages está perdendo dinheiro em um ritmo alarmante porque a maioria de seus trens está vazia. Porém, em algumas linhas, os passageiros reclamam que não cabem nos vagões e precisam esperar o próximo trem!

As autoridades querem consertar esta situação. Eles pediram a seus chefes de estação para escrever, para um determinado trem, quantas pessoas deixaram o trem em sua estação, quantas entraram e quantas tiveram que esperar. Em seguida, eles contrataram sua empresa de consultores bem pagos para atribuir trens de tamanho adequado às suas rotas.

Você acabou de receber as medições de um trem, mas antes de alimentá-las com seu algoritmo de otimização, você se lembrou de que foram coletadas em um dia de neve, então qualquer chefe de estação sensato teria preferido ficar dentro de sua cabine e calcular os números em vez de sair e contando.

Verifique seu palpite, verificando se a entrada é inconsistente, ou seja, a cada vez que o número de pessoas no trem não excedeu a capacidade nem ficou abaixo de 0 e nenhum passageiro esperou em vão. O trem deve começar e terminar a viagem vazio, em particular os passageiros não devem esperar pelo trem na última estação.

Entrada

A primeira linha contém dois inteiros C e n (2 ≤ n ≤ 100), a capacidade total e o número de estações em que o trem para. As próximas n linhas contêm três inteiros cada, o número de pessoas que deixaram o trem, entraram no trem, e teve que ficar em uma estação. As linhas são fornecidas na mesma ordem em que o trem visita cada estação. Todos os inteiros incluindo C estão entre 0 e 109 inclusive.

Saída

Uma linha contendo uma palavra: possible se as medições forem consistentes, impossible caso contrário.

Exemplos de Entrada Exemplos de Saída

1 2
0 1 1
1 0 0

possible

1 2
1 0 0
0 1 0

impossible

1 2
0 1 0
1 0 1

impossible

1 2
0 1 1
0 0 0

impossible