Las vacas, quienes tienen siempre un complejo de inferioridad acerca de sus inteligencia, tienen un nuevo juego de adivinar para afilar sus cerebros.

Una 'Vaca de Heno' se esconde detrás del establo y crea ~N~ pilas todas de distintos tamaños (convenientemente numeradas ~1..N~) de fardos de heno, cada una con ~1..1,000,000,000~ fardos de heno. Las otras vacas entonces le preguntan a la Vaca de Heno una serie de ~Q~ consultas acerca de las pilas, todas teniendo la misma forma: ¿Cuál es el menor número de fardos en cualquier pila en el rango de pilas numeradas ~Q_1..Q_h~ ?

La Vaca de Heno contesta cada una de estas preguntas con un solo entero ~A~ cuya veracidad no está garantizada.

Ayude a las otras vacas a determinar si las respuestas dadas por la Vaca de Heno son auto consistentes o si ciertas respuestas se contradicen con otras.

Entrada

• Línea 1: Dos enteros separados por espacio: ~N~ y ~Q~
• Líneas 2..Q+1: Cada línea contiene tres enteros separados por espacio que representan una sola pregunta y su respuesta: ~Q_1, Q_h~, y ~A~.

Salida

Imprima el único entero ~0~ si no hay inconsistencia entre las respuestas (esto es, si existe una realización válida de las pilas de heno que cumpla todas las ~Q~ respuestas). En otro caso, imprima el indice de ~1..Q~ de la menor pregunta cuya respuesta es inconsistente con las respuestas a las preguntas hechas antes que ella.

Restricciones

• ~1 \leq N \leq 1,000,000~
• ~1 \leq Q \leq 25,000~
• ~1 \leq Q_1 \leq Q_h \leq N~

Ejemplo de Entrada

20 4
1 10 7
5 19 7
3 12 8
11 15 12

Detalles de la Entrada: El número mínimo de fardos en las pilas 1..10 es 7, el número mínimo de fardos en las pilas 5..19 es 7, , el número mínimo de fardos en las pilas 3..12 es 8, y el número mínimo de fardos en las pilas 11..15 es 12.

Ejemplo de Salida

3

Detalles de la Salida: La Consulta 3 ("3 12 8") es la primera que no es consistente con las anteriores a ella. De las consultas 1 y 2 y le hecho de que todas las pilas de fardos tienen un número distinto de fardos, deducimos que una de las pilas 5..10 debe contener exactamente 7 fardos. Sin embargo, esta pila contradice la respuesta a la pregunta 3.