만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

진심 좌우 반복뛰기

시간 제한0.15초메모리 제한512 MB

요약
N과 K가 주어질 때 ZeroX는 K, 2K, 3K, ...를 오른쪽과 왼쪽으로 번갈아 뛰며 총 거리 N-1에서 멈춘다. 이때 최종 좌표와 바라보는 방향을 구한다.
난이도

보통10점 중 4점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

히어로 협회에는 아래와 같은 두 가지 소문이 있다.

  1. 진심 좌우 반복 뛰기를 1010010^{100}일 동안 반복하면 히어로가 된다.
  2. 뛴 거리의 총합이 NNm 이상이면 대머리가 된다.

지나가던 제로x는 소문을 듣고 진심 좌우 반복 뛰기를 하기로 결심했다. 진심 좌우 반복 뛰기는 간단하다.

  • 위치 x=0x = 0에서 시작하여, 처음에는 오른쪽으로 KKm를 뛴 다음 방향을 바꾼다.
  • 방향을 바꿀 때마다 이전에 움직인 거리에 KKm만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.

예를 들어, K=2K = 2 라면, 오른쪽으로 22m, 왼쪽으로 44m, 오른쪽으로 66m, ...

하지만, 제로x는 대머리가 되는 것이 너무나도 싫었다. 즉, 소문에 따라 뛴 거리의 총합이 NNm 이상이 되지 않아야 한다. 대머리가 되지 않으면서도 운동의 효과는 보고 싶었던 제로x는 정확히 (N−1)(N - 1)m만 뛸 것이다.

하지만 제로x는 어디서 멈춰야 하는지 계산할 수 없었다. 제로x가 대머리가 되지 않도록 도와주자!

(N−1)(N - 1)m를 뜀과 동시에 전환점에 도달할 경우, 방향을 바꾸고 멈춘다. 예제 1의 두 번째 테스트 케이스를 참고하자.

입력

첫 번째 줄에 테스트 케이스 수 TT가 주어진다. 두 번째 줄부터 TT개의 줄에는 자연수 N,KN, K가 공백으로 구분되어 주어진다.

  • 1≤T≤100,0001 ≤ T ≤ 100,000
  • 1≤N,K≤10,000,0001 ≤ N,K ≤ 10,000,000

출력

제로x가 멈춰야 하는 xx좌표와 바라보고 있게 될 방향을 출력한다. 방향을 출력할 때 오른쪽은 R, 왼쪽은 L로 나타낸다.

힌트

아래의 그림은 N=15,K=3N = 15, K = 3 인 경우의 예제이다.

총 거리가 1414인 지점의 xx좌표는 2이고, 방향은 오른쪽이다. 그래서 답은 "2 R"이다.

N=7,K=2N = 7, K = 2 인 경우, xx좌표가 −2-2인 지점에서 멈추고(2−4=−22 - 4 = -2), 방향을 바꾼다. 이후 더 이상 진행할 수 없으므로 정답은 "-2 R"이다.

예제2

  1. 예제 1

    입력
    3
    15 3
    7 2
    20 7
    
    예상 출력
    2 R
    -2 R
    -5 L
    
  2. 예제 2

    입력
    4
    1 1
    1 10000000
    10000000 1
    10000000 10000000
    
    예상 출력
    0 R
    0 R
    -607 L
    9999999 R