Вам дан массив $a$, состоящий из $n$ целых положительных чисел. Вы можете совершать над ним операцию, состоящую из следующей последовательности действий:

1. выбрать пару элементов $a_i$ и $a_j$ ($1 \le i, j \le n$ и $i \neq j$);
2. выбрать один из делителей числа $a_i$, то есть число $x$ такое, что $a_i \bmod x = 0$;
3. заменить $a_i$ на $\frac{a_i}{x}$ и $a_j$ на $a_j \cdot x$.

Например, пусть дан массив $a$ = [$100, 2, 50, 10, 1$], состоящий из $5$ элементов. Произведем над ним две операции:

1. Выберем $a_3 = 50$ и $a_2 = 2$, $x = 5$. Заменим $a_3$ на $\frac{a_3}{x} = \frac{50}{5} = 10$, $a_2$ на $a_2 \cdot x = 2 \cdot 5 = 10$. Получим массив $a$ = [$100, 10, 10, 10, 1$];
2. Выберем $a_1 = 100$ и $a_5 = 1$, $x = 10$. Заменим $a_1$ на $\frac{a_1}{x} = \frac{100}{10} = 10$, $a_5$ на $a_5 \cdot x = 1 \cdot 10 = 10$. Получим массив $a$ = [$10, 10, 10, 10, 10$].