26841번 - Reprezentacje różnicowe 다국어

Zdefiniujmy nieskończony ciąg liczb całkowitych $a_1, a_2, a_3, \dots$ w następujący sposób: $$a_n = \begin{cases} n & \text{dla }n ≤ 2 \\ 2 · a_{n-1} & \text{dla }n > 2\text{ nieparzystego} \\ a_{n-1} + r_{n-1} & \text{dla }n > 2\text{ parzystego}\end{cases}$$ przy czym $r_{n-1}$ jest najmniejszą dodatnią liczbą całkowitą niebędącą różnicą dwóch różnych elementów ze zbioru $\{a_1, a_2, \dots , a_{n-1}\}$.

Tak więc początkowe wyrazy ciągu to: $$ 1, 2, 4, 8, 16, 21, 42, 51, 102, 112, 224, 235, 470, 486, 972, 990, 1980, \dots $$

Przykładowo, aby obliczyć $a_6$, stwierdzamy, że każda z liczb $1, 2, 3, 4$ jest różnicą pewnych dwóch elementów początkowego fragmentu ciągu $1, 2, 4, 8, 16$, natomiast liczba $5$ nie jest różnicą dwóch takich elementów. Tak więc $a_6 = a_5 + 5 = 21$.

Wiadomo, że dla każdej dodatniej liczby całkowitej $x$ istnieje dokładnie jedna para indeksów $(p, q)$ taka, że $x = a_p - a_q$. Parę taką oznaczymy jako $repr(x)$. Na przykład $repr(17) = (6, 3)$ i $repr(18) = (16, 15)$. Twoim zadaniem jest wyznaczyć $repr(x)$ dla danego $x$.

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita $n$ oznaczająca liczbę przypadków testowych. W każdym z kolejnych $n$ wierszy znajduje się jedna dodatnia liczba całkowita $x$. Możesz założyć, że liczby występujące na wejściu nie powtarzają się.

Na standardowe wyjście należy wypisać $n$ wierszy. Wiersz odpowiadający liczbie $x$ z wejścia powinien zawierać $repr(x) = (p, q)$ w postaci dwóch liczb całkowitych $p$, $q$ oddzielonych pojedynczym odstępem.

• $n ≤ 100\,000$
• $x ≤ 10^9$