A permutation of a string is the set of all possible ways to combine its characters. E.g., the permutation of "abc" is {"abc", "acb", "bac", "bca", "cab", "cba"}. The size of this set is the factorial of the initial string size.

Given a string S (with up to 20 characters, all lowercase letters) and a integer N (0²N<20!) find the (N+1)^th smallest element of the permutation of S (consider the lexicographic order; the permutation of 'abc' above, for example, is represented in lexicographic order form left to right).

E.g., if S = "abc" and N=0, then the result would be "abc"

E.g., if S = "abc" and N=5, then the result would be "cba"

E.g., if S = "abc" and N=3, then the result would be "bca"

E.g., if S = "cba" and N=3, then the result would be "bca"

The input file contains one line with the number of samples and then each sample consists of two lines: one with string S and the next with number N.

For each sample, a line with the required value.

2
abc
3
abcde
119

bca
edcba

一次過真喜悅啊

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main() {
    int t, i, j, k;
    long long f[21] = {1, 1}, p;
    char str[30];
    for(i = 2; i <= 20; i++)
        f[i] = f[i-1]*i;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", str);
        int n = strlen(str);
        sort(str, str+n);
        scanf("%lld", &p);
        p++;
        int used[21] = {};
        for(i = 0; i < n; i++) {
            for(j = 0; j <= n; j++) {
                if(f[n-i-1]*j >= p)
                    break;
            }
            j--;
            p -= f[n-i-1]*j;
            for(k = 0; k < n; k++) {
                if(used[k] == 0) {
                    if(j == 0) {
                        printf("%c", str[k]);
                        used[k] = 1;
                        break;
                    }
                    j--;
                }
            }
        }
        puts("");
    }
    return 0;
}