Friar Geeglo was investigating wine cellars of CodeAbbey when he suddenly found something interesting.
Behind huge moss-covered barrel in the dark corner there was a narrow passage. Peeking there friar Geeglo discovered a small door, obviously leading to storage of long-forgotten delicious drinks!
Door has a whimsical lock - there are metal pads with letters
A B C D E F G H I J K L which can be moved so their order
is changed. It is clear - one just should arrange them all properly (i.e. guess the right permutation) - and the door
Below small inscription was scratched I've tried first
NN...N permutations in lexicographic order left by some
Brother Geeglo wants to proceed with the attempts of unlocking the door. However he do not want to check variants already tried by his predecessor (this can save him several years).
You are to help him find out which permutation he should start from.
For example, if there were only
4 letters, then
24 permutations exist and if placed in order they'll look like:
0 ABCD 1 ABDC 2 ACBD 3 ACDB 4 ADBC 5 ADCB 6 BACD 7 BADC 8 BCAD 9 BCDA 10 BDAC 11 BDCA 12 CABD 13 CADB 14 CBAD 15 CBDA 16 CDAB 17 CDBA 18 DABC 19 DACB 20 DBAC 21 DBCA 22 DCAB 23 DCBA
And if Geeglo is told that first
9 of them were already tried, he should proceed from
Input data contain the number of test-cases in the first line.
Next lines contain a single value each - the number of permutations tried by unknown monk.
Answer should contain the same amount of letter permutations - ones with which Geeglo should start in each case.
input data: 3 0 2 10531100 answer: ABCDEFGHIJKL ABCDEFGHIKJL ADLBEHICKGFJ
Note: You can find several algorithms for generating permutations in wikipedia article