Number Friends

The natural numbers are making friends! Each number is allowed to befriend another number which is a multiple of itself and does not yet have friends.

Numbers love a good order, so they take turns in a pre-determined sequence. When it is a number's turn, it will always befriend the smallest number that it is allowed to.

Here's an example of such a sequence:

1 3 1

Firstly, number $1$ would befriend the smallest multiple of itself, which is $2$. Secondly, the number $3$ would befriend the smallest multiple of itself, which is $6$. The number $1$ is in the sequence for the second time, but cannot befriend $2$ or $3$ as they already have friends, so befriends $4$ instead.

You are given a list of $N$ friendships between pairs of numbers and want to reverse engineer the order in which the friendships were made. Where there are multiple possibilities, the lexicographically smallest sequence should be given - see the explanation of the sample for an example.

Input

The first line will contain a single integer $N$, with $1 \leq N \leq 100000$.

N lines will follow, each containing two integers $a$, $b$, indicating that there is a friendship between numbers $a$ and $b$, with $a<b$ and $1 \leq a \leq 10^9$. For C++ users note that $b$ may not fit in a 32 bit integer.

Output

Print the lexicographically smallest sequence of numbers that generate the friendships in the input. It is guaranteed that at least one such sequence exists.

Subtasks

• Subtask 1 (15%): $N \leq 3$
• Subtask 2 (15%): $N \leq 4$
• Subtask 3 (30%): $N \leq 1000$
• Subtask 4 (40%): No constraints.

Explanation

There are two sequences that generate the friendships seen in the sample input, 1,3,1 and 3,1,1. The lexicographically smaller of the two is 1,3,1, so that is the output.