El nuevo establo del Granjero Juan consiste de un gran círculo de ~N~ pesebreras ~(2 \leq N \leq 3,000,000)~, numeradas ~0..N-1~, con la pesebrera ~N-1~ adyacente a la pesebrera ~0~.

Al final de cada día, las vacas de GJ vuelven al establo una por una, cada una con una pesebrera preferida que les gustaría ocupar. Sin embargo, si la pesebrera preferida de una vaca ya está ocupada por otra vaca, ella revisa secuencialmente a partir de esta pesebrera hasta que ella encuentra la primera pesebrera no ocupada, la cual ella reclama. Si al revisar ella pasa por la pesebrera ~N-1~, ella continúa revisando desde la pesebrera ~0~.

Dada la pesebrera preferida de cada vaca, por favor, determine el menor índice de pesebrera que permanece desocupado después que todas las vacas han vuelto al establo. Note que la respuesta a esta pregunta no depende del orden en que las vacas vuelven al establo.

Para evitar problemas leyendo una entrada muy grande, la entrada a este problema se da en un formato conciso usando ~K~ líneas ~(1 \leq K \leq 10,000)~ cada una de la forma:

X Y A B

Una de esas líneas especifica la pesebrera preferida para ~XY~ vacas en total: ~X~ vacas prefieren cada una de las pesebreras ~f(1)..f(Y)~, donde ~f(i) = (Ai+ B)~ mod ~N~. Los valores de ~A~ y ~B~ están en el rango ~0..1,000,000,000~.

Entrada

• Línea 1: Dos enteros separados por espacio: ~N~ y ~K~.
• Líneas 2..1+K. Cada línea contiene los enteros ~X~ ~Y~ ~A~ ~B~, interpretados como se explicó anteriormente. El número total de vacas especificados por todas esas líneas será a lo más ~N-1~. Se pueden añadir vacas a la misma pesebrera por varias de esas líneas.

Salida

El mínimo índice de una pesebrera no ocupada.

Ejemplo de Entrada

10 3
3 2 2 4
2 1 0 1
1 1 1 7

Detallas de Entrada: Hay ~10~ pesebreras en el establo, numeradas ~0..9~. La segunda línea de la entrada dice que ~3~ vacas prefieren a la pesebrera ~(2*1+4)~ mod ~10 = 6~ y ~3~ vacas prefieren la pesebrera ~(2*2+4)~ mod ~10 = 8~. La tercera línea dice que ~2~ vacas prefieren el establo ~(0*1+1)~ mod ~10 = 1~. La línea ~4~ especifica que ~1~ vaca prefiere el establo ~(1*1+7)~ mod ~10 = 8~ (entonces un total de ~4~ vacas prefieren esta pesebrera).

Ejemplo de Salida

5

Detallas de Salida: Todas las pesebreras terminan ocupadas excepto la pesebrera ~5~.

USACO 2013 November Contest, Gold Problem 1. Empty Stalls.