#!/usr/bin/env python3 import collections def solve_joust_sort(): """ Solves the Joust Sort problem by performing a topological sort on the character constraints. """ try: # 1. Read input and build the graph representation n = int(input()) # adj: adjacency list for the graph (e.g., adj['a'] = ['b'] means a < b) adj = collections.defaultdict(list) # in_degree: stores the number of incoming edges for each character in_degree = collections.defaultdict(int) for _ in range(n): line = input().split() char1, op, char2 = line[0], line[1], line[2] if op == '<': # Rule: char1 must come before char2 adj[char1].append(char2) in_degree[char2] += 1 else: # op == '>' # Rule: char2 must come before char1 adj[char2].append(char1) in_degree[char1] += 1 word = input() # 2. Get character counts and the set of unique characters from the word counts = collections.Counter(word) unique_chars_in_word = set(word) # 3. Initialize the queue for Kahn's algorithm # We start with all characters in the word that have no prerequisites (in-degree of 0). # Sorting them ensures a deterministic output when multiple solutions are possible. queue = collections.deque( sorted([c for c in unique_chars_in_word if in_degree[c] == 0]) ) sorted_chars = [] # 4. Perform the topological sort while queue: u = queue.popleft() sorted_chars.append(u) # Process neighbors of the dequeued character for v in sorted(adj[u]): # Sort neighbors for deterministic output in_degree[v] -= 1 # If a neighbor's prerequisites are met and it's in our word, add to queue if v in unique_chars_in_word and in_degree[v] == 0: queue.append(v) # 5. Check for cycles and print the result if len(sorted_chars) < len(unique_chars_in_word): # If not all characters could be sorted, a cycle exists print("IMPOSSIBLE") else: # 6. Construct the final word from the sorted character order result_parts = [char * counts[char] for char in sorted_chars] print("".join(result_parts)) except (IOError, ValueError): # Handle potential empty lines or malformed input gracefully print("IMPOSSIBLE") if __name__ == "__main__": solve_joust_sort()