Problem Description
AC is given two strings A and B, and then he wants to insert B into A. As we know, there are |A| + 1 possible ways to make the final string! For example, if A = “orz” and B = “p”, then AC may get four final strings: “porz”, “oprz”, “orpz”, “orzp”. However, these strings are not so beautiful, so AC sort them in lexicographic order, then he gets {“oprz”, “orpz”, “orzp”,”porz”}.
Now AC wants to know the k-th string in the sorted strings! For example, if AC wants to know the first string in the sorted strings, the answer is “oprz”, the second is “orpz”, the third is “orzp”, and the 4-th is “porz”.
Now you are given string A and B, and the number K, in this problem, AC guarantees that K is valid.
Input
The first line of the input data is an integer number T (T <= 1000), represent the number of test cases.
For each case, three lines follow.
The first line has one string indicates A. (Without any space in A)
The second line has one string indicates B. (Without any space in B)
The third line has one integer indicates K.
(1 <= |A|, |B| <= 10000, 1 <= K <= |A| + 1)
Output
For each test case, output a single line “Case idx:” where idx is the test case number starts from 1. Then one line output the k-th string in the sorted string.
Sample Input
4
orz
p
1
orz
p
2
orz
p
3
orz
p
4
Sample Output
Case 1:
oprz
Case 2:
orpz
Case 3:
orzp
Case 4:
porz
hash ( s[ 0..n ] ) = ( s[0]*q^n + s[1]*q^(n-1) + ...... + s[n-1]*q^1 + s[n]*q^0 ) mod p，其中，p, q 為大質(zhì)數(shù)，
適當(dāng)預(yù)處理（見函數(shù)init ）后，B 插入在 A 中任意位置所形成的字符串的任意前綴的hash 值都能 O(1) 計(jì)算出來（見函數(shù)hash）。
而最長(zhǎng)公共前綴通過二分其長(zhǎng)度，用hash值判斷是否相等，可以O(shè)(log(|A|+|B|) )得到（見函數(shù) cmp）。