Авторы загадали массив \(a\), состоящий из \(n\) целых чисел; каждое число не меньше \(2\) и не больше \(2 \cdot 10^5\). Вы не знаете его, но Вы знаете массив \(b\), который был получен из массива \(a\) при помощи следующей последовательности операций:
- Сначала весь массив \(b\) равен массиву \(a\);
- Затем для каждого \(i\) от \(1\) до \(n\):
- если \(a_i\) является простым числом, тогда число \(p_{a_i}\) добавляется в массив \(b\), где \(p\) — бесконечная последовательность простых чисел (\(2, 3, 5, \dots\));
- иначе (если \(a_i\) не является простым числом), наибольший делитель \(a_i\), не равный \(a_i\), добавляется в \(b\);
- Затем получившийся массив длины \(2n\) перемешивается и дается Вам во входных данных.
Здесь \(p_{a_i}\) означает \(a_i\)-е простое число. Первое простое число \(p_1 = 2\), второе простое число \(p_2 = 3\), и так далее.
Ваша задача — восстановить любой подходящий массив \(a\), который формирует заданный массив \(b\). Гарантируется, что ответ существует (таким образом, массив \(b\) получен из какого-либо подходящего массива \(a\)). Если существует несколько возможных ответов, Вы можете вывести любой.
Выходные данные
В единственной строке выходных данных выведите \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(2 \le a_i \le 2 \cdot 10^5\)) в любом порядке — массив \(a\), из которого можно получить массив \(b\) при помощи последовательности ходов, описанных в условии задачи. Если существует несколько возможных ответов, Вы можете вывести любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 5 2 3 2 4
|
3 4 2
|
|
2
|
1
2750131 199999
|
199999
|
|
3
|
1
3 6
|
6
|