CF1607B Odd Grasshopper

The grasshopper is located on the numeric axis at the point with coordinate $ x_0 $ . Having nothing else to do he starts jumping between integer points on the axis. Making a jump from a point with coordinate $ x $ with a distance $ d $ to the left moves the grasshopper to a point with a coordinate $ x - d $ , while jumping to the right moves him to a point with a coordinate $ x + d $ . The grasshopper is very fond of positive integers, so for each integer $ i $ starting with $ 1 $ the following holds: exactly $ i $ minutes after the start he makes a jump with a distance of exactly $ i $ . So, in the first minutes he jumps by $ 1 $ , then by $ 2 $ , 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 $ 18 $ consecutive jumps he arrives at the point with a coordinate $ 7 $ , he will jump by a distance of $ 19 $ to the right, since $ 7 $ is an odd number, and will end up at a point $ 7 + 19 = 26 $ . Since $ 26 $ is an even number, the next jump the grasshopper will make to the left by a distance of $ 20 $ , and it will move him to the point $ 26 - 20 = 6 $ . Find exactly which point the grasshopper will be at after exactly $ n $ jumps.

The first line of input contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. Each of the following $ t $ lines contains two integers $ x_0 $ ( $ -10^{14} \leq x_0 \leq 10^{14} $ ) and $ n $ ( $ 0 \leq n \leq 10^{14} $ ) — the coordinate of the grasshopper's initial position and the number of jumps.

Print exactly $ t $ lines. On the $ i $ -th line print one integer — the answer to the $ i $ -th test case — the coordinate of the point the grasshopper will be at after making $ n $ jumps from the point $ x_0 $ .

The first two test cases in the example correspond to the first two jumps from the point $ x_0 = 0 $ . Since $ 0 $ is an even number, the first jump of length $ 1 $ is made to the left, and the grasshopper ends up at the point $ 0 - 1 = -1 $ . Then, since $ -1 $ is an odd number, a jump of length $ 2 $ is made to the right, bringing the grasshopper to the point with coordinate $ -1 + 2 = 1 $ .