아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

점프

시간 제한3초메모리 제한128 MB

요약
1부터 n까지 원에 둔 수에서 k번째 수를 차례로 제거하고 마지막 세 수를 테스트 케이스마다 출력합니다.
난이도

보통10점 중 6점

유형
수학, 시뮬레이션, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

자연수 1,2,3,…,n1, 2, 3, \dots, n 이 증가하는 순서로 원 위에 놓여 있다. 이 원에서 수를 하나씩 골라 수열을 만든다. 세기는 11번 수에서 시작한다.

원에 수가 남아 있는 동안, 현재 위치에서부터 세어 kk번째 수를 고른다. 고른 수는 원에서 빼내어 수열의 뒤에 붙이고, 다음 세기는 방금 빼낸 자리의 바로 다음 수부터 다시 시작한다. 이렇게 만든 수열을 Jump(n, k)라고 한다. (단, 1≤n1 \le n, 1≤k1 \le k)

Jump(10, 2)의 처음 다섯 수는 2,4,6,8,102, 4, 6, 8, 10이다. 그 다음에는 3,7,1,9,53, 7, 1, 9, 5가 차례로 뽑히므로, Jump(10, 2) = [2, 4, 6, 8, 10, 3, 7, 1, 9, 5]이다. 같은 방식으로 Jump(13, 3) = [3, 6, 9, 12, 2, 7, 11, 4, 10, 5, 1, 8, 13], Jump(13, 10) = [10, 7, 5, 4, 6, 9, 13, 8, 3, 12, 1, 11, 2], Jump(10, 19) = [9, 10, 3, 8, 1, 6, 4, 5, 7, 2]이다.

nn과 kk가 주어질 때, Jump(n, k)의 마지막 세 수를 구하는 프로그램을 작성하시오. 예를 들어 n=10n = 10, k=2k = 2이면 1,9,51, 9, 5를 출력하면 된다. 참고로 Jump(1, k) = [1]이다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 이어지는 각 줄에는 한 테스트 케이스로 두 자연수 nn과 kk가 공백으로 구분되어 주어진다. (5≤n≤5000005 \le n \le 500000, 2≤k≤5000002 \le k \le 500000)

출력

각 테스트 케이스마다, Jump(n, k)의 뒤에서 세 번째 수, 두 번째 수, 마지막 수를 공백으로 구분하여 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    3
    10 2
    13 10
    30000 54321
    
    예상 출력
    1 9 5
    1 11 2
    10775 17638 23432
    
  2. 예제 2

    입력
    3
    13 3
    10 19
    13 10
    
    예상 출력
    1 8 13
    5 7 2
    1 11 2