题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Reprezentacje różnicowe

我们来定义一个无穷整数序列 $a_{1}, a_{2}, a_{3}, \ldots$，规则如下：

$$a_{n} = \begin{cases} n & \text{若 } n \leq 2 \\ 2 \cdot a_{n-1} & \text{若 } n > 2 \text{ 且为奇数} \\ a_{n-1} + r_{n-1} & \text{若 } n > 2 \text{ 且为偶数} \end{cases} $$

其中 $r_{n-1}$ 是集合 $\left\{a_{1}, a_{2}, \ldots, a_{n-1}\right\}$ 中任意两个不同元素之差未出现过的最小正整数。

序列的前几项是：

$$1, 2, 4, 8, 16, 21, 42, 51, 102, 112, 224, 235, 470, 486, 972, 990, 1980, \ldots $$

举个例子，要算 $a_{6}$，我们先看前五项 $1, 2, 4, 8, 16$。它们的差值包括 $1, 2, 3, 4$，但 $5$ 未出现，因此 $a_{6} = a_{5} + 5 = 21$。

已知对于任意正整数 $x$，都存在唯一一对下标 $(p, q)$ 满足 $x = a_{p} - a_{q}$，记为 $\operatorname{repr}(x)$。比如 $\operatorname{repr}(17) = (6, 3)$，$\operatorname{repr}(18) = (16, 15)$。你的任务是为给定的 $x$ 找出 $\operatorname{repr}(x)$。

输入格式

输入第一行是一个整数 $n$，表示测试数据数量。

接下来的 $n$ 行，每行一个正整数 $x$。假设输入中的数不重复。

输出格式

输出 $n$ 行，每行对应输入中的 $x$，包含 $\operatorname{repr}(x) = (p, q)$，以两个整数 $p$ 和 $q$表示。

2
17
18

6 3
16 15

对于 $17$，$a_{6} - a_{3} = 21 - 4 = 17$，所以 $\operatorname{repr}(17) = (6, 3)$；对于 $18$，$a_{16} - a_{15} = 990 - 972 = 18$，所以 $\operatorname{repr}(18) = (16, 15)$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 1000, x \leq 10^{9}$，结果 $p$ 和 $q$ 不超 100	$20$
$2$	$n, x \leq 1000$
$3$	$n, x \leq 1000000$
$4$	$n \leq 100000, x \leq 10^{9}$	$40$