Rar the Cat is visiting the arcade with his friends. He has came across a very interesting arcade machine, named Bishi Bashi. The machine contains a wide variety of competitive minigames, based on bashing various buttons.
The machine in the arcade caters for up to 3 players. However, Rar the Cat is only here with Jacq the Dinosaur. Nevertheless, they decide to give the game a try.
One of the minigames involves bashing buttons to kill a particular monster. The monster will be killed after Rar the Cat and Jacq the Dinosaur presses the buttons X times.
While playing this particular minigame, Rar the Cat manages to press his button once every R milliseconds while Jacq the Dinosaur manages to press her button once every J milliseconds. Both Rar and Jacq will press their buttons once at the 0th millisecond. Subsequently, Rar the Cat will press once at every multiple of R milliseconds and Jacq the Dinosaur will press once at every multiple of J milliseconds.
As they are too engrossed in their button bashing, Rar the Cat and Jacq the Dinosaur did not notice which one of them delivered the 'final blow' to the monster. The 'final blow' is the last press of the button which manages to kill the monster. If both Rar and Jacq presses the button at the exact same moment and the monster dies, both of them are considered to have killed the monster.
They have played a total of N rounds of the above minigame and want you to figure out who delivered the 'final blow' for each of the rounds. For each round, there will be a different value of R, J and X, with the ith round having Ri, Ji and Xi respectively.
For all testcases, 0 < Ri, Ji, Xi ≤ 109 unless otherwise indicated in the subtasks.
Subtask 1 (2%): 1 ≤ N ≤ 20. However, all Ri = Ji.
Subtask 2 (29%): 1 ≤ N ≤ 20, 0 < Ri, Ji, Xi ≤ 103.
Subtask 3 (18%): 1 ≤ N ≤ 20, 0 < Xi ≤ 106.
Subtask 4 (20%): 1 ≤ N ≤ 500000. However, all of the N rounds will have the same value of R and J. In other words, all Ri = R1 and all Ji = J1 for all i > 1.
Subtask 5 (31%): 1 ≤ N ≤ 500000.
Subtask 6 (0%): Sample Testcases.
The first line of input will contain one integer, N.
The next N lines of input will contain 3 integers each. The ith line will contain Ri, Ji followed by Xi.
For each of the N rounds, output "R" if Rar the Cat delivered the 'final blow' and output "J" if Jacq the Dinosaur delivered the 'final blow'. If the 'final blow' was delivered by the both of them, output "RJ". You are to output the result for each round on a different line, one on each line.
10 2 4 1 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 2 4 7 2 4 8 2 4 9 2 4 10
RJ RJ R RJ RJ R RJ RJ R RJ
At time 0, Rar and Jacq would have pressed the button simultaneously. Hence, any monster whose X = 1 or 2 will be killed by both of them at the same time, at time 0.
At time 2, Rar will press the button once. Any monster whose X = 3 will be killed by him.
At time 4, Rar and Jacq would have pressed at the same time. Monster with X = 4 or 5 are killed by both of them.
At time 6, Rar will press the button once, alone. Any monster whose X = 6 will be killed only by him.
At time 8, Rar and Jacq presses the button together, killing any monster whose X = 7 or 8.
At time 10, Rar will press the button alone, killing X = 9.
At time 12, Rar and Jacq will press the buttons together, killing X = 10 or 11.