Description

As an easy warm-up problem, to help contestants better show their speed, Mystia provides a brief statement of the problem: Gap Transfer.

---

In the dream, Yuyuko came to the Night Sparrow Restaurant. Perhaps due to the incident, Yuyuko, already a big eater, has now become even more terrifying.

Mystia will cook a total of $n$ dishes to satisfy all customers and try to increase her chance of survival. These dishes are numbered $0,1,2$ up to $n-1$. Meanwhile, Yuyuko will place orders $k$ times.

• In this problem, we define an ordering event as $\operatorname{order}(t,x)$, meaning the customer makes a request to Mystia, hoping she will cook and serve dish $x$ at time $t$.
• We use a triple $(t_i,x_i,y_i)$ to describe Yuyuko’s $i$-th ordering. In each ordering, Yuyuko will issue $\operatorname{order}(t_i,x_i)$. However, Yuyuko’s desire cannot be satisfied. Therefore, when Yuyuko receives the dish at time $t_i$, she will issue $\operatorname{order}(2\cdot t_i,(x_i+y_i)\bmod n)$ again! Even worse, this process keeps accumulating: then she will issue $\operatorname{order}(3\cdot t_i,(x_i+2\cdot y_i)\bmod n)$ and even more...
• In summary, Yuyuko’s $i$-th ordering $(t_i,x_i,y_i)$ will perform the following operations:

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

Since Yuyuko will issue infinitely many orders, it is impossible for Mystia to satisfy her. But to live up to everyone’s expectations, Mystia decides to delay as long as possible. As the owner, she has amazing cooking skills:

• At every moment, Mystia can cook infinitely many copies of a dish, but the dish can only be of one single type.

If at some time the dish Yuyuko orders is not cooked immediately (Yuyuko is not willing to eat a dish cooked at the previous moment), then she will fly into a rage and immediately destroy the Night Sparrow Restaurant at that time. Mystia wants to know how long she can hold on (how long means the maximum number of moments she can survive such that within these moments Yuyuko will not destroy the restaurant; time is counted starting from $1$). If she can hold on for $9961^{9961}$ moments or more (in this problem, you may treat $9961^{9961}$ as infinity), output Mystia will cook forever....

Input Format

The first line contains two integers $n,k$, with meanings as described above.

The next $k$ lines each contain three integers $(t_i,x_i,y_i)$, describing one query.

Output Format

Output one line. Output the maximum time Mystia can hold on, or output Mystia will cook forever....

4 3
2 1 2
3 1 1
4 2 1

3

2 2
2 1 2
3 0 1

Mystia will cook forever...

Hint

Sample 1 Explanation

At time $4$, Yuyuko ordered dish $3$ and dish $2$ at the same time, so the Night Sparrow Restaurant will be destroyed, and the answer is $4-1=3$.

---

Constraints and Notes

$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{k} & \bm{\max\{t_i\}} & \textbf{特殊性质} & \textbf{分值}\cr\hline \textsf1 & =1 & \text{无特殊限制} & \text{无} & 10 \cr\hline \textsf2 & \leq 10 & \leq 10 & \text{无} & 20 \cr\hline \textsf3 & \text{无特殊限制} & \text{无特殊限制} & \text{A} & 30\cr\hline \textsf4 & \text{无特殊限制} & \text{无特殊限制}& \text{无}& 40 \cr\hline \end{array}$$

Special property $\text{A}$: It is guaranteed that for all $i$, $y_i = 0$.

For $100\%$ of the testdata:

• $1 \le t_i,n \leq 10 ^ 9$.
• $0 \le x_i,y_i \leq 10 ^ 9$.
• $1 \le k \leq 1000$.

Translated by ChatGPT 5