Los $K(1\le K\le 1,000)$ macheteros de una brigada millonaria de la zafra azucarera están participando en una competencia de lectura. La competencia consiste en leer un solo libro con $N(1\le N\le 100,000)$ páginas tan rápido como sea posible entendiéndolo.

El machetero $i$ tiene una velocidad de lectura de $S_i(1\le S_i\le 100)$ páginas por minuto, un tiempo máximo de lectura consecutiva de $T_i(1\le Ti\le 100)$ minutos, y un tiempo mínimo de descanso de $R_i(1\le R_i\le 100)$ minutos. El machetero puede leer a un ritmo de Si páginas por minuto, pero solo por $T_i$ minutos al tiempo. Después él se detiene para descansar, debe descansar por Ri minutos antes de comenzar a leer nuevamente.

Escriba el programa read que determine el número de minutos (redondeados hasta el minuto completo más cercano) que le tomará a cada machetero para leer el libro.

Entrada

Línea 1: Dos enteros separados por espacio: $N$ y $K$.

Líneas 2..K+1: La línea i+1 contiene tres enteros separados por espacios: $S_i,T_i$ y $R_i$.

Salida

Líneas 1..K+1: La línea i debe indicar cuántos minutos (redondeados hasta el minuto completo más cercano) se requieren para que cada machetero i lea todo el libro.

Ejemplo de Entrada

10 3
2 4 1
6 1 5
3 3 3

Ejemplo de Salida

6
7
7

Detalles de la Entrada

El libro tiene 10 páginas; están compitiendo 3 macheteros. El primer machetero lee con una velocidad de 2 páginas por minuto, puede leer a lo más 4 minutos al tiempo, y debe descansar por 1 minuto después de leer. El segundo machetero lee con una velocidad de 6 páginas por minuto, puede leer a lo más 1 minuto al tiempo, y debe descansar 5 minutos después de leer. El último lee con una velocidad de 3 páginas por minuto, puede leer a lo más 3 minutos a tiempo, y debe descansar 3 minutos después de leer.

Detalles de la Salida

El primer machetero puede leer 8 páginas en 4 minutos, descansar por 1 minuto, y leer las últimas 2 páginas en un minuto. El segundo lee 6 páginas en un minuto, descansa por 5 minutos, y termina en el siguiente minuto. El último lee 9 páginas en 3 minutos, descansa por 3 minutos, y termina en el siguiente minuto.