UVa 941 - Permutations

// UVa 941 - Permutations

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;

typedef unsigned long long ull;

int main() {

	ull fact[20];
	fact[0] = 1;
	for (int i = 1; i < 20; i++)
		fact[i] = fact[i - 1] * i;

	int t;
	for (cin >> t; t; t--) {
		string st;
		ull m;
		cin >> st >> m;

		vector<char> remaining(st.begin(), st.end());
		sort(remaining.begin(), remaining.end());

		int n = st.length();
		string sol(st);
		for (int i = 0; i < n; i++) {
			int idx = m / fact[n - i - 1];
			sol[i] = remaining[idx];
			for (int j = idx; j + 1 < remaining.size(); j++)
				remaining[j] = remaining[j + 1];
			remaining.pop_back();
			m -= idx * fact[n - i - 1];
		}

		cout << sol << endl;
	}
	return 0;
}