Infinity Table
Contest: Codeforces Round 739 (Div. 3)
Difficulty rating: 800
Tags: implementation, math

Polycarp has found a table having an infinite number of rows and columns. The rows are numbered from $$$1$$$, starting from the topmost one. The columns are numbered from $$$1$$$, starting from the leftmost one.

Initially, the table hasn't been filled and Polycarp wants to fix it. He writes integers from $$$1$$$ and so on to the table as follows.

The figure shows the placement of the numbers from $$$1$$$ to $$$10$$$. The following actions are denoted by the arrows.

The leftmost topmost cell of the table is filled with the number $$$1$$$. Then he writes in the table all positive integers beginning from $$$2$$$ sequentially using the following algorithm.

First, Polycarp selects the leftmost non-filled cell in the first row and fills it. Then, while the left neighbor of the last filled cell is filled, he goes down and fills the next cell. So he goes down until the last filled cell has a non-filled neighbor to the left (look at the vertical arrow going down in the figure above).

After that, he fills the cells from the right to the left until he stops at the first column (look at the horizontal row in the figure above). Then Polycarp selects the leftmost non-filled cell in the first row, goes down, and so on.

A friend of Polycarp has a favorite number $$$k$$$. He wants to know which cell will contain the number. Help him to find the indices of the row and the column, such that the intersection of the row and the column is the cell containing the number $$$k$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of one line containing one integer $$$k$$$ ($$$1 \le k \le 10^9$$$) which location must be found.

Output format:
For each test case, output in a separate line two integers $$$r$$$ and $$$c$$$ ($$$r, c \ge 1$$$) separated by spaces — the indices of the row and the column containing the cell filled by the number $$$k$$$, respectively.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
7
11
14
5
4
1
2
1000000000

Example output:
2 4
4 3
1 3
2 1
1 1
1 2
31623 14130

Editorial:
Let's call a set of cells being filled from the topmost row to the leftmost column a layer. E. g. the $$$1$$$-st layer consists of the single number $$$1$$$, the $$$2$$$-nd layer consists of the numbers $$$2$$$, $$$3$$$ and $$$4$$$, the $$$3$$$-rd layer consists of the numbers $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$ and $$$9$$$, etc.
The number of cells in layers forms an arithmetic progression. The first layer consists of $$$a_1 = 1$$$ cells, the $$$i$$$-th layer consists of $$$a_i = a_{i-1} + 2$$$ cells. The minimum number in the $$$i$$$-th layer $$$x_i$$$ is equal to the sum of sizes of all layers from the $$$1$$$-st to the $$$(i - 1)$$$-th plus $$$1$$$.
Suppose that $$$k$$$ belongs to the $$$i$$$-th layer. Consider the value of $$$m = k - x_i + 1$$$. Polycarp fills exactly $$$i$$$ cells on the $$$i$$$-th layer before he starts filling the cells from the right to the left (i. e. while he goes down). Therefore, if $$$m \le i$$$, the number $$$k$$$ belongs to the $$$m$$$-th row and the $$$i$$$-th column. Otherwise, the number belongs to the $$$i$$$-th row and the $$$(i - (m - i))$$$-th column.
Consider a way to find the coordinates of a given number $$$k$$$. Let's iterate by the layer number $$$i$$$ to which given the number belongs calculating the values of $$$a_i$$$ and $$$x_i$$$ (going to the next layer, let's calculate the next layer parameters as follows: $$$x_{i + 1} := x_i + a_i$$$; $$$a_{i + 1} := a_i + 2$$$). The iteration must be stopped if the layer number $$$i$$$ is such that $$$x_i \le k < x_{i + 1}$$$. Using the values of $$$i$$$ and $$$x_i$$$, we can calculate the given number's coordinates in the described way in $$$O(1)$$$. The total time of calculating the coodrinates for one given $$$k$$$ is $$$O(i_k)$$$ where $$$i_k$$$ is the number of the layer to which the given $$$k$$$ belongs.
Let's represent the value of $$$x_i$$$ as $$$x_i = f(i)$$$: $$$x_i = 1 + \sum\limits_{j = 1}^{i - 1} a_j = 1 + \sum\limits_{j = 1}^{i - 1} (2j - 1) = 1 + \frac{1 + 2(i - 1) - 1}{2} \cdot (i - 1) = 1 + (i - 1)^2$$$. $$$1 + (i_k - 1)^2 = x_{i_k} \le k < x_{i_k + 1} = 1 + i_k^2$$$, hence $$$i_k \approx \sqrt(k)$$$. Therefore, the coordinates of one number $$$k$$$ may be calculated in $$$O(\sqrt{k})$$$. At the same time, as it follows from the formulas, the layer number $$$i_k$$$ can be calculated as follows: $$$i_k = \lceil \sqrt{k} \rceil$$$ (the square root of $$$k$$$ rounded up). To avoid accuracy problems, you can calculate the value using a loop.