Problem Statement

Little Lisa has been invited to a holiday party with her friends. So that everyone receives a gift, the host of the party has decided to give presents through a "Yankee swap".

In this version of a Yankee swap (which may differ from the version that you are used to), each person begins holding a present; the first person (indexed from 1) holds present 'A', the second person holds present 'B', etc. Each guest in turn (starting with guest 1 and ending with guest N) decides whether or not he wants to swap presents. If he decides to swap, he chooses a person to swap with, and the chosen person cannot reject the swap. When every person has had a turn, the Yankee swap is over, and each person leaves with the gift they are holding.

For example, one way that the party (with 3 people) could proceed is as follows:

"ABC" --> Person 1 swaps with person 2 --> "BAC"
"BAC" --> Person 2 does not swap       --> "BAC"
"BAC" --> Person 3 swaps with person 2 --> "BCA"

In the above example, person 1 leaves with present B, person 2 leaves with present C, and person 3 leaves with present A.

The guests at the party have given you their preferences, where the i-th element corresponds to the preference list of the i-th guest. If a guest ends up with the gift in the j-th position of his preference list, he will have an unhappiness of j. Each guest knows the preferences of all other guests. Each guest will act optimally to minimize his own unhappiness, and knows all other guests will do the same. If there are multiple ways for a guest to minimize his own unhappiness, he will choose not to swap at all if possible; if there are still multiple ways, he will choose to swap with the guest with the lowest index.

Return a String, the i-th character of which corresponds to the turn of the i-th person. If the i-th person did not swap in his turn, the i-th character of the result must be equal to '-'. If he did swap with the k-th person, the i-th character of the result must be equal to the k-th lowercase letter (so, 'a' corresponds to swapping with the first person, 'b' to the second and so on).

Definition

Constraints

Examples