Problema F: Medições adocicadas


image copo_graduado

Ufa, mas que calor! No refeitório da escola, a Mariana está a fazer experiências com sumo de laranja. Em cada experiência, ela coloca um copo graduado sobre a prateleira da máquina do sumo e abre a torneira. A cada segundo, o nível do sumo no copo sobe uma quantidade inteira positiva K. Repare que o copo pode não começar vazio. Assim, sendo o nível que o sumo apresentava inicialmente no copo um inteiro não negativo I, no momento em que a Mariana abre a torneira o nível do sumo é I, um segundo depois é I+K, dois segundos depois é I+2K, e assim por diante.

Após um intervalo de tempo pré-determinado, a experiência acaba. Pode considerar que a capacidade do copo é suficiente para conter todo o sumo durante a experiência, isto é, em nenhum momento o conteúdo do copo transborda.

O objetivo da Mariana é, a cada segundo, observar o nível de sumo que o copo marca e anotá-lo no seu caderno. Acontece que, no final de cada experiência, um pouco de sumo caiu sobre o caderno, tornando alguns dos valores da sequência ilegíveis. Que trapalhada! Se ao menos a Mariana tivesse rabiscado em algum lado os valores de I e de K...

É capaz de ajudar a Mariana a confirmar que a sequência por ela apontada antes de sujar o caderno com sumo poderia realmente ser válida ou dizer se, com o calor que fazia, ela se enganou?

Tarefa

Escreva um programa que, dada a sequência de valores apontados pela Mariana no seu caderno, possivelmente com alguns valores ilegíveis, determina se a sequência original poderia ser válida.

Input

A primeira linha do input contém um inteiro, E, que corresponde ao número de experiências (independentes) realizadas. Para cada experiência, é fornecida a seguinte informação:
  • A primeira linha relativa a uma experiência contém um inteiro, N, que é o tamanho da sequência apontada no caderno.
  • A segunda linha contém uma sequência de N inteiros, separados por um espaço. Cada elemento da sequência é um número entre -1 e 1,000,000. Os elementos que ficaram ilegíveis com o sumo são representados com o valor -1.

Restrições

  1  ≤  E  ≤  10 Número de experiências
  1  ≤  N  ≤  10,000 Tamanho de uma sequência
 

Output

O output tem uma linha por cada experiência, pela ordem definida no input. Cada linha tem a palavra: "Possivel" (sem aspas nem acento), se houver pelo menos uma forma de a respetiva sequência original ser válida; "Impossivel" (sem aspas nem acento), no caso contrário.

Exemplo

Input 

5
3
4 -1 6
3
4 5 6
3
4 -1 4
5
-1 -1 4 6 -1
3
-1 -1 -1

Output 

Possivel
Possivel
Impossivel
Possivel
Possivel

Explicação

  • Na primeira experiência, o sumo tornou ilegível o segundo elemento da sequência, que poderia ser 5.
  • Na segunda experiência, o sumo não tornou ilegível nenhum dos elementos da sequência e ela é válida, com I=4 e K=1.
  • Na terceira experiência, se os valores apontados estivessem corretos, a torneira teria de ter estado fechada durante a experiência.
  • Na quarta experiência, a sequência original poderia ser 0 2 4 6 8.
  • Na quinta experiência, 7 20 33 é uma das sequências originais válidas possíveis.


ToPAS'2022
193.136.122.94