P5968 [POI 2017] Difference Representations

Given a sequence $a$: - When $n \le 2$, $a_n = n$. - When $n > 2$ and $n$ is odd, $a_n = 2 \times a_{n-1}$. - When $n > 2$ and $n$ is even, $a_n = a_{n-1} + r_{n-1}$. Here, $r_{n-1} = \operatorname{mex}(|a_i - a_j|)(1 \le i \le j \le n - 1)$, and $\operatorname{mex}\left\{ S \right\}$ denotes the smallest non-negative integer that is not in the set $S$. The first several terms of the sequence $a$ are: $1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980$. It can be proven that for any positive integer $x$, there exists a unique pair of integers $(p, q)$ such that $x = a_p - a_q$, which is defined as $\operatorname{repr}(x)$. For example, $\operatorname{repr}(17) = (6, 3)$, and $\operatorname{repr}(18) = (16, 15)$. Now there are $n$ queries. Each query gives a positive integer $x$. For each query, output $\operatorname{repr}(x)$.

The first line contains a positive integer $n$. The next $n$ lines each contain a positive integer $x$, representing a query.

Output $n$ lines. Each line contains two positive integers $p, q$, answering each query in order.

For $100\%$ of the testdata, $1 \le n \le 10^5$, and $1 \le x \le 10^9$. Translated by ChatGPT 5