P7921 [Kubic] Division

It is recommended to read the background of Problem F first.

You have a **multiset**. Initially, it contains only one positive integer $n$. Each time, you may choose a positive integer $x$ currently in the multiset and remove it, then specify a positive integer $y$ (it does not need to be in the multiset) such that $x>y$, and insert $y$ and $x-y$ into the multiset. You must ensure that **at any moment**, the maximum value in the multiset is **strictly less than** $2$ times the minimum value in the multiset. Find the **maximum** number of operations you can perform, and **output a construction**. **The input guarantees that the maximum number of operations does not exceed $10^6$.**

A single line containing one integer $n$.

The first line contains one integer $m$, the number of operations in your constructed plan. The next $m$ lines each contain two integers $x,y$, describing one operation (the meanings of $x,y$ are the same as in the statement). You must ensure that $x>y$ and that $x$ has appeared in the current multiset.

For $100\%$ of the testdata, $1\le n\le 10^9$. ## Constraints ||Score|$n$| |:-:|:-:|:-:| |$\operatorname{Subtask}1$|$10$|$\le 10$| |$\operatorname{Subtask}2$|$20$|$\le 100$| |$\operatorname{Subtask}3$|$30$|$\le 10^6$| |$\operatorname{Subtask}4$|$40$|No special limits| ### Scoring In the following cases, you will get $0$ points on that test point: - The output format does not meet the requirements. - Extra information is printed (including spaces and newline characters). - The number of operations in your construction is different from the standard answer. - Your construction does not satisfy the requirements of the problem. - Time limit exceeded. If none of the above happens, you will get full score on that test point. **It is guaranteed that the SPJ uses no more than $100\operatorname{ms},10\operatorname{MB}$.** ### Sample Explanation 1 One possible sequence of operations is as follows: `8` `3 5` `2 3 3` It can be proven that there is no better plan. ### Sample Explanation 2 One possible sequence of operations is as follows: `30` `12 18` `8 10 12` `6 6 8 10` `5 5 6 6 8` `4 4 5 5 6 6` It can be proven that there is no better plan. Translated by ChatGPT 5