问题
让我们定义一个严格的全序关系 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