When all the presents are delivered to the children, Santa Claus goes home to take some rest. Then, the most exciting part of the day begins - Santa starts making garlands. A garland is a sequence of lamps connected with a wire. You are given a String lamps containing the available lamps. Each element is formatted "color size" (quotes for clarity), where color is a string representing the lamp's color, and size is an integer representing the lamp's size. A garland must contain every available lamp, and every pair of consecutive lamps in a garland must have different sizes.
Santa will make every possible garland using these lamps. Each time he makes a garland, he will turn it on for a while and then disassemble it to make another one. Every garland he makes will be different. Two garlands are different if they have different lamps in at least one position. Santa will make one garland before another if it has a bigger first lamp. In case of a tie, he will choose the garland whose first lamp's color comes earlier alphabetically. If both garlands have the same first lamp, he will make his choice according to the second lamp, and so on. He will go to sleep after making all possible garlands.
Return a String containing the n-th garland Santa will make, where n is a 1-based index. The return String should be a permutation of the String lamps. If Santa will make less than n garlands, return an empty String instead.