The goal of this problem is to implement a text ciphering (加密) method: the Jinkela Trio transform (JTT).
Besides the input string S to be ciphered, JTT also requires an integer parameter K. Here, we take S=”banana”, and K=7122 to explain the ideas of JTT.
Step 1.
Let N be the size of the input string (in our example N = 6). We create an array G[N] using K and the special prime number:
P = 233811181 (hexadecimal: 0xdefaced)
as follows:
X = K;
int i=0;
for(;i<N;++i){
X = (X*P+1) % 4294967296;
G[i] = X%N;
}
Note to use unsigned or long long to avoid overflow.
In this example:
G[6] = {1,0,5,2,3,0};
Step 2.
Create a 2d NxN array Q, where Q[0] (the 0-th row) corresponds to the input string S, and Q[i] (0 < i < N) corresponds to a circular left shift of i positions with respect to the input string S. For S="banana", we obtain the following array Q:
0 1 2 3 4 5 0 b a n a n a 1 a n a n a b 2 n a n a b a 3 a n a b a n 4 n a b a n a 5 a b a n a n
Step 3.
Do the following:
int i;
for(i=0;i<N;++i){
if G[i]!=G[(i+1)%N], then swap the two rows: Q[G[i]] and Q[G[(i+1)%N]].
}
For our example, after the above step 3, we can obtain Q as follows:
0 1 2 3 4 5 0 b a n a n a 1 a n a n a b 2 a n a b a n 3 a b a n a n 4 n a b a n a 5 n a n a b a
Finally, the result of the JTT method is the last column (i.e. column N-1) of array Q.
In our example, the last column of Q is "abnnaa". Therefore, JTT outputs "abnnaa".
The first line contains two integers T, K (T<=100,1<=K<=2147483647), indicating that there’re T test cases, all of which take K as the parameter for JTT. For the next T lines, each contains a string consisting of lower case English letters as the input string for JTT to cipher. The length of the input strings will be <= 1000.
Output the results of JTT for the test cases, one string per line.
Note that you need to print a newline character ‘\n’ at the end of each line.