A

Lexicographic Order Input: Standard Input Output: Standard Output

 

The alphabet of a certain alien language consists of n distinct symbols. The symbols are like the letters of English alphabet but their ordering is different. You want to know the original order of the symbols in that particular alphabet. You have a string consists of all the letters of that alphabet and you know that this is the k-th (1 based) lexicographic permutation of these symbols. You have to arrange these symbols in lexicographic order of that language.

 

Input

The first line of input will contain an integer T (T ≤ 5000) which denotes the number of test cases.

 

Each of the following T lines contains a string s and an integer k. The string will be of length n (1 ≤ n ≤ 20) and will consist of lowercase letters only. All the letters in the string will be distinct. The value of k will be in the range (1 ≤ k ≤ n!).

 

Output

For each line of input output the case number and a string which contains the letters in lexicographic order in that language.

 

Sample Input                              Output for Sample Input

3 bdac 11 abcd 5 hjbrl 120

Case 1: abcd Case 2: acdb Case 3: lrbjh

Note

The first input resembles the original order of English alphabet. Here are the lexicographic permutations

abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca

1 2 3 4 5 6 7 8 9 10 11 12

cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba

13 14 15 16 17 18 19 20 21 22 23 24

---

這題先把基本的字典順序生出來, 但是題目給定的字典順序是不一樣的,
因此我們只要映射的方式即可,
例如 hjbrl 120, 假使按照原本的想法 b < h < j < l < r
120 對應 rljhb －　那麼 b -> l, h -> r, j -> b, l-> j, r -> h
因此答案就是 lrbjh

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
    int t, cases = 0, i, j;
    long long f[50] = {1};
    for(i = 1; i < 50; i++)
        f[i] = f[i-1] * i;
    scanf("%d", &t);
    while(t--) {
        char buf[50];
        long long n;
        scanf("%s %lld", buf, &n);
        printf("Case %d: ", ++cases);
        string s(buf);
        sort(s.begin(), s.end());
        int len = strlen(buf);
        int ans[50] = {}, used[50] = {};
        for(i = 0; i < len; i++) {
            int cnt = 0;
            while(n > f[len-i-1]) {
                n -= f[len-i-1];
                cnt++;
            }
            cnt++;
            for(j = 0; j < len; j++) {
                if(!used[j])    cnt--;
                if(cnt == 0) {
                    used[j] = 1;
                    ans[i] = s[j];
                    break;
                }
            }
        }
        for(i = 0; i < len; i++) {
            for(j = 0; j < len; j++) {
                if(ans[j] == s[i]) {
                    printf("%c", buf[j]);
                }
            }
        }
        puts("");
    }
    return 0;
}