Problem 5

4

1 votes
Recruit, Easy, Ready, Mathematics, Approved, Factorization
Problem

Agent Encrypto has gone undercover into the enemy territory of CryptoLand to learn their battle plans. His handler Agent Decrypto has hacked their mail servers but he is unable to understand any of the information because it is encrypted in a very secret language called CryptoPerm. It is up to Agent Encrypto now to protect the Nation from the enemies. And he has to hurry because the enemies are starting to get suspicious.

Agent Encrypto has found out that CryptoPerm code works in the following ways:

  • CryptoPerm uses only lowercase alphabets
  • The alphabet set(original_set) is replaced by its encrypted form(encrypted_set) which is actually a permutation of the original_set.
  • Some of the alphabets encri are initially chosen and it is fixed that each of them will be replaced by an alphabet decri
  • Of all the possible permutations of the encrypted_set(given that some letters are fixed), the Kth lexicographically smallest such permutation is used.

You have been hired to solve this problem because of your coding skills. Your mission, should you choose to accept is given all encri, all decri and K, you need to find the encrypted form of the alphabet which is the CryptoPerm code. We hope you can save the day.

Input:

First line contains T which is the number of test cases.

Each test case contains 3 lines.

First line of every test case contains a string containing all the encri.
Second line of every test case contains a string containing all the decri.
Third line contains an integer K, indicating which permutation of all the possibilities is the CryptoPerm code of the alphabet.

Output:

For each test case, output a line containing the representation of the alphabet in CryptoPerm.
If the corresponding permutation does not exist, print "Not possible!"(without the quotes) instead.

Constraints:

  • 1 ≤ T ≤ 10000
  • 1 ≤ length of string containing all the encri = length of string containing all the decri ≤ 26
  • 1 ≤ K ≤1018

Scoring:

  • 1 ≤ T ≤ 10, 1 ≤ K ≤ 10 : (30 pts)
  • 1 ≤ T ≤ 100, 1 ≤ K ≤ 1000 : (30 pts)
  • Original Constraints : (40 pts)
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Case 1: The alphabets b,c,d have already been mapped to be represented by x,y,z respectively. Now we need to find the lexicographically smallest(as K=1) permutation of the alphabet. This is done if we assign each remaining alphabet to the earliest possible position in the permutation. Hence the answer is axyzbcdefghijklmnopqrstuvw.

Case 2: After fixing the given letters in position, 3 letters a,y,z are yet to be mapped. They can be mapped by some permutation of b,y,z. The different permutations of these 3 letters are byz, bzy, ybz, yzb, zby, zyb. Using the 2nd smallest possibility, we get our answer bacdefghijklmnopqrstuvwxzy

Editor Image

?