Dance Around the Clock (Large)

A ballroom owner painted a circular clock face on the dance floor. D dancers numbered 1 through D stand on that circle: dancer 1 at the 12:00 position, and every other dancer in increasing numerical order going clockwise. The number of dancers is even.

The dance lasts N turns. On turn $i$ (counting from 1) this happens.

• If $i$ is odd, the dancer at the 12:00 position swaps places with the next dancer in clockwise order. Going past those two, the next pair of dancers in clockwise order swaps, and so on all the way around the circle, until every dancer has taken part in exactly one swap.
• If $i$ is even, the dancer at the 12:00 position swaps places with the next dancer in counterclockwise order. Going past those two, the next pair of dancers in counterclockwise order swaps, and so on all the way around the circle, until every dancer has taken part in exactly one swap.

The diagram below shows the starting arrangement and two turns of a dance with eight people.

Which two dancers stand next to dancer number K when the dance is over?

The first line has one integer T, the number of test cases. Each of the next T lines has three integers D, K, and N: the number of dancers, the number of the dancer you are asked about, and the number of turns the dance lasts.

Limits

• $1 \le T \le 100$
• $4 \le D \le 10^8$
• $D$ is even
• $1 \le K \le D$
• $1 \le N \le 10^8$

For each test case print one line of the form Case #x: y z.

• x is the test case number, starting from 1.
• y is the number of the dancer standing to dancer K's left when the dance is over, that is, one step away in clockwise order.
• z is the number of the dancer standing to dancer K's right, that is, one step away in counterclockwise order.

Left and right are read from the dancer's own point of view, so left is one step clockwise around the circle and right is one step counterclockwise. It helps to think only in terms of clockwise and counterclockwise.

In the first sample case eight dancers dance one turn, and dancer 6 ends to dancer 3's left while dancer 4 ends to dancer 3's right. In the second sample case eight dancers dance two turns, and dancer 1 ends to dancer 4's left while dancer 7 ends to dancer 4's right. In the third sample case four dancers dance eight turns, which brings the circle back to its starting arrangement, so dancer 2 is to dancer 1's left and dancer 4 is to dancer 1's right.

Both D and N reach $10^8$, so simulating the turns one by one is far too slow.