P7835 “Wdoi-3” Night Sparrow Dreaming

As Yuyuko, who sits at the top of the food chain in Gensokyo, she has always been the nightmare of the owner Mystia. Even though Yuyuko usually would not choose to eat her, still, what you think about in the day shows up in your dreams at night. Mystia had a dream, a dream mixed with fantasy and reality. Or rather, it was the reality within fantasy... Although Mystia does not know when that day will come, she dares not lower her guard, so the owner asks you for help...

As an easy warm-up problem, to help contestants better show their speed, Mystia provides a brief statement of the problem: [Gap Transfer](https://www.luogu.com.cn/paste/2dwm3f7z). --- 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...`.

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 one line. Output the maximum time Mystia can hold on, or output `Mystia will cook forever...`.

#### 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