URI Online Judge | 2185

Jugando con Pomekons

Por Gabriel Duarte, UNIFESO BR Brazil

Tiempo límite: 1

Luego de capturar varios pomekons, Dabriel y Guarte decidieron crear un juego con las pequeñas criaturas y quien gane el juego, se quedará con todas las criaturas.

El juego funciona de la siguiente manera: Todos los pomekons son separados en N pilas, las mismas no necesariamente tienen el mismo número de criaturas, el jugador de turno elije una pila y remueve uno o mas pomekons. El juego termina cuando no hay criaturas para ser seleccionadas, y el jugador de esta vuelta es considerado perdedor.

Como Dabriel siempre es el primero en jugar y en las últimas vueltas ha estado ganando, Guarte sospecha que Dabriel descubrió algún truco del juego, entonces, propuso una nueva regla. En la nueva versión del juego, Guarte seleccionará tres enteros X, Y, y V, y el número de criaturas en cada pila entre X y Y, tendrá una V cantidad de pomekons. Dabriel aceptó la propuesta, pero solicitó de su ayuda para decirle si el tendrá posibilidad de ganar siempre que haya un cambio en las pilas. Como Dabriel y Duarte son muy buenos en este juego, puede asumir que ambos juegan de la mejor manera posible.

Entrada

La primera línea consta de dos enteros N (1 ≤ N ≤ 10⁵) y M (1 ≤ M ≤ 10⁵) que representan la cantidad de pilas y cantidad de cambios que se efectúan, respectivamente.
La segunda línea consta de N enteros vi (1 ≤ iN, 0 ≤ vi ≤ 10⁴), representando la cantidad de pokemones que cada pila i contiene.
Las siguientes M líneas constan de 3 enteros X, Y, V (1 ≤ X YN, 1 ≤ V ≤ 10⁴), que describen los cambios que Guarte realizará.

Salida

Por cada cambio en las celdas del juego, usted deberá imprimir "Possivel" si Dabriel tiene posibilidad de ganar, o "Impossivel", en caso contrario.

Ejemplo Entrada Ejemplo Salida

8 6
1 2 3 4 5 6 7 8
4 6 5
7 8 0
1 8 0
1 1 1
1 1 8
1 8 5

Possivel
Possivel
Impossivel
Possivel
Possivel
Impossivel