Adela and Bastian are fans of riddles, and they recently came up with a new game, but they need your help to play it.
In this game, Adela first chooses a secret word $$$s = s_1s_2\ldots s_N$$$ of length $$$N$$$, formed by $$$N$$$ lowercase letters of the English alphabet $$$s_1, s_2, \dots, s_N$$$. Bastian knows the length $$$N$$$ of the secret word, but not the word itself.
To win the game, Bastian must determine whether the word chosen by Adela is periodic or not. To do this, Bastian can choose two integers $$$L$$$ and $$$R$$$, and ask the following question: Is $$$t = s_Ls_{L+1}\ldots s_R$$$ a period of $$$s$$$? Adela will always answer each question truthfully.
Adela and Bastian consider that $$$t$$$ is a period of a word $$$s$$$ if and only if $$$s$$$ can be obtained by concatenating $$$c \geq 2$$$ copies of $$$t$$$.
A word $$$s$$$ is periodic if $$$t$$$ is a period of $$$s$$$ for some $$$t$$$. For example: ab is the only period of abab, and both a and aa are periods of aaaa, while on the other hand ab and ababa are not periodic.
To make the game fun, Adela must set a limit on the number of questions that Bastian can ask. This limit must depend on the initial information that Bastian receives: the value of $$$N$$$. In particular, she wants the limit on questions $$$K$$$ to be the minimum possible, but in such a way that Bastian can win the game if he asks the $$$K$$$ questions optimally, having absolute certainty of always being able to find the correct answer, regardless of which word of length $$$N$$$ Adela chooses.
Help them to play their game by writing a program that, given the value of $$$N$$$, finds the limit on questions $$$K$$$ that they should use. Additionally, so that Bastian does not think that Adela cheated in case he loses, the program must indicate a set of $$$K$$$ questions with which Bastian could win.
A line with an integer $$$N$$$ $$$(2 \leq N \leq 10^6)$$$, the length of the word $$$s$$$ chosen by Adela.
A line with the integer $$$K$$$, indicating the limit of questions they should use. Then $$$K$$$ lines indicating a set of questions with which Bastian could win. The $$$i$$$-th line describes the $$$i$$$-th question using the integers $$$L$$$ and $$$R$$$ $$$(1 \leq L \leq R \leq N)$$$, as explained above.
If there are multiple sets of optimal questions, any of them will be accepted.
4
1 1 2
6
2 3 4 4 6
A word of length $$$4$$$, $$$s = s_1s_2s_3s_4$$$, is periodic if and only if $$$t = s_1s_2$$$ is a period of $$$s$$$. Therefore, in the first example, one question is sufficient to determine with certainty whether $$$s$$$ is a periodic word or not.
