B - n-th Points Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

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