ACPC10H - Jumping Beans

N jumping beans are standing in a line. At each second, a bean jumps. Your assignment is to figure the final position of the beans after a given number of seconds. To make the explanation easier, let’s assign a unique letter to each bean, and for simplicity, let’s assume the beans are initially standing in order: A, B, C, etc. To simplify even further, let’s assume N = 4, so initially the beans are standing in the order ABCD. At the first second, A jumps, swapping its place with B. Now the order is BACD. At the second second, it’s B’s turn, but this time swapping its place with A, then C, resulting in the standing order ACBD. More formally: at second s, the left most bean that has jumped the least number of times will do the swap s times, each time swapping its place with the bean on its right. Note that when the right-most bean swaps, it moves to the left-most position, pushing everybody else one place to the right. So, continuing with the previous example, and starting with the arrangement ACBD, it is bean C’s turn, since it is the left-most bean that has jumped the least amount of times. Being at the third second, C will swap three times, first resulting in ABCD, then ABDC, and then CABD. At the fourth second, it’s bean D’s turn to jump. At the fifth second, and since all the four beans have jumped exactly once, the bean that will jump is the bean standing at the left-most position.

Input

Your program will be tested on one or more test cases. Each test case is specified on a single line specifying an integer T and a string S where (0 < T < 109 ) is the number of seconds and S is the initial arrangement of the beans. S is a non empty string made of different upper-case letters (’A’. . . ’Z’).
The last test case is followed by a line having a single 0.

Output

For each test case, print the following line:
k. S
Where k is the test case number (starting at one,) and S is the arrangement of the beans after jumping for T seconds.

Example

Input:
3 ABCD
13 ACM
0

Output:
1. CABD
2. CAM

Added by:Omar ElAzazy
Date:2010-11-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACPC 2010

hide comments
2022-11-14 10:51:04
Poor English. It's better and simpler to print all 4 transitions from ABCD.
2017-07-12 11:04:51
yes, assert(str.size() < 27) passed
2011-05-07 07:59:20 Gurpreet Singh
"S is a non empty string made of different upper-case letters (’A’. . . ’Z’).".......
Does that mean that the length of string has to be less than 27 ???
2011-04-14 05:36:38 Pratham Khandelwal
What is the limit for string length?
2011-03-31 17:41:27 hosam samy
note that (0
Omar ElAzazy: Fixed

Last edit: 2010-11-30 20:34:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.