Problem 1: Decryption

Aliens are planning to attack on Earth. Scientists at ISRO got a breakthrough when they were able to intercept the message being transferred in between aliens, but the problem is that aliens are using a technique for encrypting the message. Codefest team of IT-BHU were able to hack into the systems of aliens and decipher the method, the aliens were using for encryption but a method for decryption has not been found yet. You are required to decrypt the message.

The method used for encryption is explained below:
Consider a string of N alphabets for example encrypt (N=7). The string is treated as if the last character wraps around back to the first. Next consider a set S of N different strings, in which each string is formed by cyclic rotation of the alphabets of the original string. So for the string encrypt, S = {encrypt, ncrypte, crypten, ryptenc, yptencr, ptencry, tencryp}

The next step is to perform a lexicographical sort in decreasing order on the set of above strings. So S becomes {yptencr, tencryp, ryptenc, ptencry, ncrypte, encrypt, crypten}

Now, the encyrpted string of N alphabets is formed taking the last character from the above sorted strings. For given example, the encrypted string is rpcyetn. They also send the position of the first character of the encrypted string so that the message can be decrypted i.e. 5 for the given example.

Input

There is a single integer T<=200 on the first line of input which denotes the number of test cases to follow. Each of the next T lines, contains a string made up of k alphabets (a-z characters only) followed by an integer N, separated by a blankspace. 1<=N<=k<=3000.

Output

Output consists of T lines, each containing the decrypted string.

Sample Input:

3
rpcyetn 5
rathe 5
aabb 2

Sample Output

encrypt
earth
abab

Solution

The problem is based on Burrows Wheeler Transform, BWT, which is used for data compression. Let we have the string as "DRDOBBS". After applying BWT, we get "OBRSDDB"

Now, to get the original string what we require is a Transformation Vector. The transformation vector, T, is an array with one index for each row in column F. For a given row i, T[ i ] is defined as the row where S[ i + 1 ] is found where S is the array of original sring. Row 3 contains S0, the original input string, and row 5 contains S1, the string rotated one character to the left. Thus, T[ 3 ] contains the value 5. S2 is found in row 2, so T[ 5 ] contains a 2. For this particular matrix, the transformation vector can be calculated to be { 1, 6, 4, 5, 0, 2, 3 }.

Thus, given a copy of L, we have a copy of F as column F contains the all the characters of the string in sorted order. Now, we form a transformation vector with copy of L and F. The character 'O' in row 0 clearly moves to row 4 in column F, which means T[ 4 ] = 0. But what about row 1? The 'B' could match up with either the 'B' in row 0 or row 1. Since by definition the strings in F must appear in sorted order, it means that all the strings that start with a common character in L appear in the same order in F, although not necessarily in the same rows. Because of this, we know that the 'B' in row 1 of L is going to move up to row 0 in F. The 'B' in row 6 of L moves to row 1 of F. The complexity of this problem is O(n).

Note: The above solution can be applied if we take the input strings in reverse order.

[CPP Code] [Test Case]

Reference:

• Burrows Wheeler Transform