Mystia's Dilemma

In this problem, Mystia faces an endless stream of orders. There are n dishes numbered from 0 to n-1, and each order is issued as an event of the form $$\operatorname{order}(t,x)$$ at a given moment. In particular, for each of the k orders described by a triple \( (t_i,x_i,y_i) \), an infinite sequence of orders is triggered:

$$\operatorname{order}(j\cdot t_i,\ (x_i+(j-1)\cdot y_i)\bmod n)\quad\text{for}\quad j=1,2,3,\ldots$$

At any time moment (the time moments are counted starting from 1), Mystia can cook an unlimited number of dishes, but they all must be of the same kind. If at a given moment the orders that arrive specify different dish types (i.e. they are not all identical), the customer (Youmu) will become furious and immediately destroy the restaurant.

Your task is to determine the maximum number of consecutive moments (starting from moment 1) during which Mystia can avoid disaster by choosing an appropriate dish type at each moment. If she can last for at least $$9961^{9961}$$ moments (in this problem, you may consider $$9961^{9961}$$ as infinity), then output Mystia will cook forever....

---

Note: An order from a given triple \( (t_i,x_i,y_i) \) appears at time \( m \) if and only if \( t_i\mid m \). At such a moment, the dish requested is computed as

$$f_i(m)=\bigl(x_i+\Bigl(\frac{m}{t_i}-1\Bigr)\cdot y_i\bigr)\bmod n. $$

For the moment to be safe, all orders arriving at that moment (if any) must request the same dish.

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁵), representing the number of dish types and the number of initial orders respectively. Each of the following k lines contains three integers t_i, x_i, and y_i (1 ≤ t_i ≤ 10⁵, 0 ≤ x_i,y_i < n</sup>), describing an order event.

outputFormat

If Mystia can safely serve orders for at least $$9961^{9961}$$ moments, output Mystia will cook forever.... Otherwise, output the maximum moment T (starting from 1) such that for every moment \( 1\le m\le T \), all orders arriving at time m are identical (or no order arrives).

sample

7 1
3 1 2

Mystia will cook forever...