蚱蜢位于数字轴上坐标为 $$$x_0$$$ 的点。
由于无事可做,他开始在轴上的整数点之间跳跃。从坐标为 $$$x$$$ 的点向左跳跃 $$$d$$$ 会将蚱蜢移动到坐标为 $$$x - d$$$ 的点,而向右跳跃则将其移动到坐标为 $$$x + d$$$ 的点。
蚱蜢非常喜欢正整数,因此对于从 $$$1$$$ 开始的每个整数 $$$i$$$ ,以下内容成立:在开始后恰好 $$$i$$$ 分钟,他以恰好 $$$i$$$ 的距离跳跃。因此,在最初的几分钟里,他跳了 $$$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$$$ 行上打印一个整数 - 第 $$$i$$$ 测试用例的答案 - 从点 $$$x_0$$$ 跳跃 $$$n$$$ 后蚱蜢将到达的点的坐标。
示例
输入 #1
9 0 1 0 2 10 10 10 99 177 13 10000000000 987654321 -433494437 87178291199 1 0 -1 1
输出 #1
-1 1 11 110 190 9012345679 -87611785637 1 0
注意
示例中的前两个测试用例对应于从 $$$x_0 = 0$$$ 点开始的前两次跳转。
由于 $$$0$$$ 是偶数,因此长度 $$$1$$$ 的第一次跳跃向左进行,蚱蜢最终到达点 $$$0 - 1 = -1$$$。
然后,由于 $$$-1$$$ 是奇数,因此向右进行长度 $$$2$$$ 的跳跃,将蚱蜢带到坐标 $$$-1 + 2 = 1$$$ 的点。