问题

我们在直角坐标系上定义了两个不同点$P(x_1,y_1)$、$Q(x_2,y_2)$之间的严格全序关系，如下所示。

• 如果 $|x_1|+|y_1|\\neq|x_2|+|y_2|$ 并且 $|x_1|+|y_1|<|x_2|+|y_2|$，则 $P<Q$
• 如果 $|x_1|+|y_1|=|x_2|+|y_2|$ 并且 $x_1\\neq{x_2}$ 且 $x_1＜x_2$，则 $P＜Q$
• 如果 $|x_1|+|y_1|=|x_2|+|y_2|$ 并且 $x_1=x_2$ 且 $y_1＜y_2$，则 $P＜Q$
• 否则，$P>Q$

你的任务是回答许多查询问题：“当按照上述定义的关系对所有整数点阵$\\mathbb{Z}^2$进行升序排序时，输出第$n$（从$1$开始计数）个元素”。

输入

输入数据按照下列格式给出。

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

• 第一行是一个整数$Q (1 \\leq Q \\leq 100,000)$，表示查询的数量。
• 接下来的$Q$行，每行包含一个查询的信息。第$i$行（$1 \\leq i \\leq Q$）包含一个整数$n_i (1 \\leq n_i \\leq 10^{18})$，表示第$i$个查询的数字$n$。

输出

输出$Q$行，每行包含一个查询的答案，按照输入中查询的顺序排列。请确保在最后一行结尾处插入一个换行符。

输入示例 1

7
1
2
3
4
5
6
1000000000000000000

输出示例 1

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