35248번 - Joust Sort 스페셜 저지다국어

We are going to organise the letters of the word using a novel algorithm based on the natural instincts of the hoarse chestnut tree: a grand tournament between its constituent letters.

We will pick several pairs of letters and have them face off. The result of a match between these letters determines their relative order. For example, if $a < b$, then all occurrences of $a$ in a well-organised word should come before all occurrences of $b$ in that word. If there is no case for $a < b$ or $b < a$, then the individual letters $a$ and $b$ may intersperse among each other in any order.

Given a word, and several such matches, determine a fair rearrangement of the word to meet all of the constraints given. It is possible that multiple such rearrangements exists, or that none exist at all.

• One line containing the number of orders to follow, $n$ ($1 \le n \le 700$).
• $n$ further lines, each containing a distinct ordering of two lowercase letters $a$ and $b$ separated by a < or > character and spaces.
• One final line containing the word to improve, $s$ ($1 \le |s| \le 100,000)$.

Output a sorted version of the word, or IMPOSSIBLE if the word cannot be sorted according to all of the rules at once.

In case there are multiple answers, you may output any one of them.