← 返回题目列表

AtCoder · code_festival_china_b

B. 第 n 个点

中文机器翻译题面 查看原题

问题

让我们定义一个严格的全序关系 2 不同点 P(x_1,y_1),Q(x_2,y_2) 在直角坐标平面上如下。

  • If |x_1|+|y_1|\neq|x_2|+|y_2| 和 |x_1|+|y_1|<|x_2|+|y_2| 然后 P<Q
  • If |x_1|+|y_1|=|x_2|+|y_2| 和 x_1\neq{x_2} 和 x_1<x_2 然后 P<Q
  • If |x_1|+|y_1|=|x_2|+|y_2| 和 x_1=x_2 和 y_1<y_2 然后 P<Q
  • 如果不然的话, P>Q

你的任务是回答许多询问,“当你对所有整数格的集合进行排序时 \mathbb{Z}^2 按上面定义的关系升序,输出 n-th (1-索引)元素。”


输入

输入按以下格式给出

Q
n_1
n_2
:
n_Q
  • 在第一行,您将得到一个整数 Q (1 \leq Q \leq 100,000),查询次数。
  • 关于以下内容 Q 行,每行包含每个查询的信息。 i-th (1 \leq i \leq Q) 行包括 n_i (1 \leq n_i \leq 10^{18}),号码 n 的 i第一个查询。

输出

输出 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