Problem

Let us define an strict total order relation between $2$ distinct points $P(x_1,y_1)$,$Q(x_2,y_2)$ on a rectangular coordinate plane as following.

• If $|x_1|+|y_1|\\neq|x_2|+|y_2|$ and $|x_1|+|y_1|<|x_2|+|y_2|$ then $P<Q$
• If $|x_1|+|y_1|=|x_2|+|y_2|$ and $x_1\\neq{x_2}$ and $x_1＜x_2$ then $P＜Q$
• If $|x_1|+|y_1|=|x_2|+|y_2|$ and $x_1=x_2$ and $y_1＜y_2$ then $P＜Q$
• If else, $P>Q$

Your task is to answer many queries that asks, "When you sort the set of all the integer lattice $\\mathbb{Z}^2$ in ascending order by the relation defined above, output the $n$-th ($1$-indexed) element."

Input

Input is given in the following format

$Q$ $n_1$ $n_2$ : $n_Q$

• On the first line, you will be given an integer $Q (1 \\leq Q \\leq 100,000)$, the number of queries.
• On the following $Q$ lines, each line contains the information of each query. The $i$-th $(1 \\leq i \\leq Q)$ line consists of $n_i (1 \\leq n_i \\leq 10^{18})$, the number $n$ of the $i$-th query.

Output

Output $Q$ lines, each line containing the answer to each query in the order the queries appear in the input. Make sure to insert a line break at the end of the last line.

Input Example 1

7
1
2
3
4
5
6
1000000000000000000

Output Example 1

0 0
-1 0
0 -1
0 1
1 0
-2 0
263818038 443288743