Remove Duplicate Strings While Preserving Order

You are given a list of strings. Your task is to remove any duplicate strings while preserving the order of their first occurrence.

The input starts with an integer n which indicates the number of strings, followed by n lines each containing one string.

You should output the unique strings in a single line, separated by a single space.

In mathematical terms, if the input list is \( S = [s_1, s_2, \dots, s_n] \), you need to compute a list \( U \) such that \[ U = [s_{i_1}, s_{i_2}, \dots, s_{i_k}] \quad \text{where } s_{i_j} \neq s_{i_l} \text{ for } j \neq l \quad \text{and } i_1 < i_2 < \dots < i_k. \]

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 1000), the number of strings. Each of the next n lines contains a non-empty string. The strings may consist of letters and are case-sensitive.

outputFormat

Output a single line containing the unique strings in their original order, separated by a single space.

1
apple

apple