题目链接：Problem - B - Codeforces

The grasshopper is located on the numeric axis at the point with coordinate x0x0.

Having nothing else to do he starts jumping between integer points on the axis. Making a jump from a point with coordinate xx with a distance dd to the left moves the grasshopper to a point with a coordinate x−dx−d, while jumping to the right moves him to a point with a coordinate x+dx+d.

The grasshopper is very fond of positive integers, so for each integer ii starting with 11 the following holds: exactly ii minutes after the start he makes a jump with a distance of exactly ii. So, in the first minutes he jumps by 11, then by 22, and so on.

The direction of a jump is determined as follows: if the point where the grasshopper was before the jump has an even coordinate, the grasshopper jumps to the left, otherwise he jumps to the right.

For example, if after 1818 consecutive jumps he arrives at the point with a coordinate 77, he will jump by a distance of 1919 to the right, since 77 is an odd number, and will end up at a point 7+19=267+19=26. Since 2626 is an even number, the next jump the grasshopper will make to the left by a distance of 2020, and it will move him to the point 26−20=626−20=6.

Find exactly which point the grasshopper will be at after exactly nn jumps.

Input

The first line of input contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases.

Each of the following tt lines contains two integers x0x0 (−1014≤x0≤1014−1014≤x0≤1014) and nn (0≤n≤10140≤n≤1014) — the coordinate of the grasshopper's initial position and the number of jumps.

Output

Print exactly tt lines. On the ii-th line print one integer — the answer to the ii-th test case — the coordinate of the point the grasshopper will be at after making nn jumps from the point x0x0.

Example

input

Copy

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

output

Copy

-1
1
11
110
190
9012345679
-87611785637
1
0

Note

The first two test cases in the example correspond to the first two jumps from the point x0=0x0=0.

Since 00 is an even number, the first jump of length 11 is made to the left, and the grasshopper ends up at the point 0−1=−10−1=−1.

Then, since −1−1 is an odd number, a jump of length 22 is made to the right, bringing the grasshopper to the point with coordinate −1+2=1−1+2=1.

题意：当前位置为奇数的时候往右边跳，反之往左边跳

思路：刚开始为奇数的时候，（0往右跳）， 1往右跳， 2往左跳， 3往左跳， 4往右跳， 5往右跳

2右，2左循环往复，为偶数的时候反之。求和可以用求和公式的推导式

#include<bits/stdc++.h>
using namespace std;int main(){int t;cin >> t;long long x0, n;while(t--){cin >> x0 >> n;long long a = n / 2;long long x = x0;;if(x0 & 1){if(a & 1){x += (0 + a - 1) * ((a - 1) / 2 + 1) / 2 * 4 + ((a - 1) / 2 + 1);x -= (1 + a - 2) * (a / 2) / 2 * 4 + (a / 2);if(n & 1){x -= n + n - 1;;}else{x -= n;}}else{x += (0 + a - 2) * (a / 2) / 2 * 4 + (a / 2);if(n & 1){x += n + n  - 1;}else{x += n;}if(a != 0){x -= (1 + (a - 1)) * ((a - 1) / 2 + 1) / 2 *4 +  ((a - 1) / 2 + 1);}}}else{if(a & 1){x -= (0 + a - 1) * ((a - 1) / 2 + 1) / 2 * 4 + ((a - 1) / 2 + 1);x += (1 + a - 2) * (a / 2 + 1 - 1) / 2 * 4 + (a / 2);if(n & 1){x += n + n - 1;}else{x += n;}}else{x -= (0 + a - 2) * (a / 2) / 2 * 4 + (a / 2);if(n & 1){x -= n + n - 1; }else{x -= n;}if(a != 0){x += (1 + (a - 1)) * ((a - 1) / 2 + 1) / 2 *4 +  ((a - 1) / 2 + 1);}}}cout << x << endl;}return 0;
}