Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Broken Chain

Limits: 1s, 256 MB

Jahid loves Motorbikes. He really wants to have a bike of his own. So he requests his elder brother Jadu to buy him a bike. But knowing the risks of riding a bike, Jadu doesn’t want Jahid to even go near bikes. So he tells Jahid If he can come up with a problem that Jadu can’t solve, Jadu will buy him a bike.

Jahid thought of a problem about Bike chains. He will take a broken chain of some length and insert one end of the chain to some rotator. He will then lift the rotator up so that the chain becomes vertically straight due to gravity. Then he will rotate the rotator counter-clockwise a certain number of times. During the rotations, the position of the other end of the chain will be determined by gravity. See the images below for better understanding. Given length of the chain and the number of rotations, Jahid asks Jadu to tell him what will be the final position of the other end of the chain after the rotations. The center of the coordinate system is the rotating end of the chain.

Input

First line of input contains the number of test case T (1 <= T <= 100000). Next T lines contain T test case with N , R ( 1 ≤ N ≤ 109 , 1 ≤ R ≤ 1018 ) where N is the length of the chain and R is the number of rotations.

Output

For each test case, print X Y the position of the other end of the chain.

Samples

InputOutput
6
6 0
6 1
6 2
6 3
6 4
6 5
0 -5
1 -4
1 -2
1 0
0 1
1 -4

Authors
Discussion
Submit

Login to submit