시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 65 20 11 31.429%

문제

자연수 1,2,3,...,n이 그림과 같이 증가하는 순서로 원을 만들고 있다. 창영이는 원에서 수를 하나씩 골라 수열을 만드려고 한다. 시작은 1번이다. 수에 수가 없을 때까지, k번째 수를 계속 선택해 원에서 제거하고, 수열에 추가한다. 이렇게 만든 수열을 Jump(n,k)라고 한다. (1 ≤ n,k)

Jump(10,2)의 처음 다섯 수는 2, 4, 6, 8, 10이다. 그 다음에는 3, 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]이다.

n과 k가 주어졌을 때, Jump(n,k)의 마지막 세 숫자를 구하는 프로그램을 작성하시오. n=10, k=2인 경우 1,9,5를 출력하면 된다. Jump(1,k) = [1]이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄이고 두 자연수 n과 k가 주어진다. (5 ≤ n ≤ 500,000, 2 ≤ k ≤ 500,000)

출력

각 테스트 케이스에 대해서, 뒤에서 세 번째 수, 두 번째 수, 첫 번째 수를 공백으로 구분하여 출력한다.

예제 입력 1

3
10 2
13 10
30000 54321

예제 출력 1

1 9 5
1 11 2
10775 17638 23432
W3sicHJvYmxlbV9pZCI6Ijg5MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTBcdWQ1MDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc5MFx1YzVmMFx1YzIxOCAxLDIsMywuLi4sblx1Yzc3NCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjNmQwXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM2ZDBcdWM1ZDBcdWMxMWMgXHVjMjE4XHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFjZThcdWI3N2MgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzJkY1x1Yzc5MVx1Yzc0MCAxXHViYzg4XHVjNzc0XHViMmU0LiBcdWMyMThcdWM1ZDAgXHVjMjE4XHVhYzAwIFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAsIGtcdWJjODhcdWM5ZjggXHVjMjE4XHViOTdjIFx1YWNjNFx1YzE4ZCBcdWMxMjBcdWQwZGRcdWQ1NzQgXHVjNmQwXHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YWNlMCwgXHVjMjE4XHVjNWY0XHVjNWQwIFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YjljY1x1YjRlMCBcdWMyMThcdWM1ZjRcdWM3NDQgSnVtcChuLGspXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBuLGspPFwvcD5cclxuXHJcbjxwPkp1bXAoMTAsMilcdWM3NTggXHVjYzk4XHVjNzRjIFx1YjJlNFx1YzEyZiBcdWMyMThcdWIyOTQgMiwgNCwgNiwgOCwgMTBcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgMywgNywgMSwgOSwgNVx1Yjk3YyBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBKdW1wKDEwLDIpID0gWzIsNCw2LDgsMTAsMyw3LDEsOSw1XVx1Yzc3NFx1YjJlNC4gSnVtcCgxMywzKSA9IFszLDYsOSwxMiwyLDcsMTEsNCwxMCw1LDEsOCwxM11cdWM3NzRcdWFjZTAsIEp1bXAoMTMsMTApID0gWzEwLDcsNSw0LDYsOSwxMyw4LDMsMTIsMSwxMSwyXSwgSnVtcCgxMCwxOSkgPSBbOSwxMCwzLDgsMSw2LDQsNSw3LDJdXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2p1bXAoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA2cHg7IHdpZHRoOjI1NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPm5cdWFjZmMga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBKdW1wKG4saylcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzEzOCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIG49MTAsIGs9Mlx1Yzc3OCBcdWFjYmRcdWM2YjAgMSw5LDVcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gSnVtcCgxLGspID0gWzFdXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yzc3NFx1YWNlMCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4IG5cdWFjZmMga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICg1ICZsZTsgbiAmbGU7IDUwMCwwMDAsIDIgJmxlOyBrICZsZTsgNTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjRhNFx1YzVkMFx1YzExYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzIxOCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMTgsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKdW1wIiwiZGVzY3JpcHRpb24iOiI8cD5JbnRlZ2VycyAxLDIsMywgJmhlbGxpcDssIG4gYXJlIHBsYWNlZCBvbiBhIGNpcmNsZSBpbiB0aGUgaW5jcmVhc2luZyBvcmRlciBhcyBpbiB0aGUgZm9sbG93aW5nIGZpZ3VyZS4gV2Ugd2FudCB0byBjb25zdHJ1Y3QgYSBzZXF1ZW5jZSBmcm9tIHRoZXNlIG51bWJlcnMgb24gYSBjaXJjbGUuIFN0YXJ0aW5nIHdpdGggdGhlIG51bWJlciAxLCB3ZSBjb250aW51YWxseSBnbyByb3VuZCBieSBwaWNraW5nIG91dCBlYWNoIGstdGggbnVtYmVyIGFuZCBzZW5kIHRvIGEgc2VxdWVuY2UgcXVldWUgdW50aWwgYWxsIG51bWJlcnMgb24gdGhlIGNpcmNsZSBhcmUgZXhoYXVzdGVkLiBUaGlzIGxpbmVhcmx5IGFycmFuZ2VkIG51bWJlcnMgaW4gdGhlIHF1ZXVlIGFyZSBjYWxsZWQgSnVtcChuLGspIHNlcXVlbmNlIHdoZXJlIDEgJmxlOyBuLCBrLjxcL3A+XHJcblxyXG48cD5MZXQgdXMgY29tcHV0ZSBKdW1wKDEwLDIpIHNlcXVlbmNlLiBUaGUgZmlyc3QgNSBwaWNrZWQgbnVtYmVycyBhcmUgMiwgNCwgNiwgOCwgMTAgYXMgc2hvd24gaW4gdGhlIGZvbGxvd2luZyBmaWd1cmUuIEFuZCAzLCA3LCAxLCA5IGFuZCA1IHdpbGwgZm9sbG93LiBTbyB3ZSBnZXQgSnVtcCgxMCwyKSA9IFsyLDQsNiw4LDEwLDMsNywxLDksNV0uIEluIGEgc2ltaWxhciB3YXksIHdlIGNhbiBnZXQgZWFzaWx5IEp1bXAoMTMsMykgPSBbMyw2LDksMTIsMiw3LDExLDQsMTAsNSwxLDgsMTNdLCBKdW1wKDEzLDEwKSA9IFsxMCw3LDUsNCw2LDksMTMsOCwzLDEyLDEsMTEsMl0gYW5kIEp1bXAoMTAsIDE5KT1bOSwxMCwzLDgsMSw2LDQsNSw3LDJdLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2p1bXAoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA2cHg7IHdpZHRoOjI1NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdSB3cml0ZSBhIHByb2dyYW0gdG8gcHJpbnQgb3V0IHRoZSBsYXN0IHRocmVlIG51bWJlcnMgb2YgSnVtcChuLGspIGZvciBuLCBrIGdpdmVuLiBGb3IgZXhhbXBsZSBzdXBwb3NlIHRoYXQgbj0xMCwgaz0yLCB0aGVuIHlvdSBzaG91bGQgcHJpbnQgMSwgOSBhbmQgNSBvbiB0aGUgb3V0cHV0IGZpbGUuIE5vdGUgdGhhdCBKdW1wKDEsayk9WzFdLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgdGhlIGlucHV0IGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIG4gYW5kIGssIHdoZXJlIDUgJmxlOyBuICZsZTsgNTAwLCBhbmQgMiAmbGU7IGsgJmxlOyA1MDAsMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IHRoZSBsYXN0IHRocmVlIG51bWJlcnMgb2YgSnVtcChuLGspIGluIHRoZSBvcmRlciBvZiB0aGUgbGFzdCZuYnNwO3RoaXJkLCBzZWNvbmQgYW5kIHRoZSBsYXN0IGZpcnN0LiBUaGUgZm9sbG93aW5nIHNob3dzIHNhbXBsZSBpbnB1dCBhbmQgb3V0cHV0IGZvciB0aHJlZSB0ZXN0IGNhc2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2009 E번