题目描述

蚱蜢位于数轴上坐标为 $x_0$ 的点。

由于无事可做，它开始在数轴上的整数点之间跳跃。从坐标为 $x$ 的点以距离 $d$ 向左跳，会使蚱蜢到达坐标为 $x - d$ 的点，而向右跳则会到达坐标为 $x + d$ 的点。

蚱蜢非常喜欢正整数，因此对于每个从 $1$ 开始的整数 $i$，都有如下规律：在开始后的第 $i$ 分钟，它会跳跃距离恰好为 $i$ 的一步。所以，在第 $1$ 分钟它跳 $1$，然后跳 $2$，以此类推。

跳跃的方向由以下规则决定：如果蚱蜢跳跃前所在点的坐标是偶数，则向左跳；否则向右跳。

例如，如果连续跳了 $18$ 步后，蚱蜢到达坐标为 $7$ 的点，那么它将以距离 $19$ 向右跳，因为 $7$ 是奇数，最终到达 $7 + 19 = 26$。由于 $26$ 是偶数，下一步它将以距离 $20$ 向左跳，移动到 $26 - 20 = 6$。

请你计算，经过恰好 $n$ 次跳跃后，蚱蜢会停在数轴上的哪个点。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

接下来的 $t$ 行，每行包含两个整数 $x_0$（$-10^{14} \leq x_0 \leq 10^{14}$）和 $n$（$0 \leq n \leq 10^{14}$），分别表示蚱蜢的初始坐标和跳跃次数。

输出格式

输出恰好 $t$ 行。对于第 $i$ 个测试用例，输出一个整数，表示从 $x_0$ 出发跳跃 $n$ 次后蚱蜢所在点的坐标。

说明/提示

示例中前两个测试用例对应于从 $x_0 = 0$ 开始的前两次跳跃。

由于 $0$ 是偶数，第一次长度为 $1$ 的跳跃向左进行，蚱蜢到达 $0 - 1 = -1$。

然后，由于 $-1$ 是奇数，长度为 $2$ 的跳跃向右进行，蚱蜢到达 $-1 + 2 = 1$。

由 ChatGPT 4.1 翻译

样例

9
0 1
0 2
10 10
10 99
177 13
10000000000 987654321
-433494437 87178291199
1 0
-1 1

-1
1
11
110
190
9012345679
-87611785637
1
0