Вам было предложено сыграть в игру. В данной игре возможно \(n\) исходов, на каждый из которых вы должны поставить некоторое целое количество монет. В случае, если \(i\)-й исход окажется выигрышным, вы получите обратно количество монет в размере вашей ставки на этот исход, умноженной на \(k_i\). Обратите внимание, что ровно один из \(n\) исходов окажется выигрышным.
Ваша задача — сказать, как распределить монеты так, чтобы при любом выигрышном исходе выйти в плюс. Более формально, суммарное количество монет, которое вы поставили на все исходы, должно быть строго меньше числа монет, полученных обратно при каждом возможном выигрышном исходе.
Выходные данные
Для каждого набора входных данных выведите \(-1\), если требуемого способа распределить монеты не существует. Иначе выведите \(n\) целых чисел \(x_1, x_2,\ldots, x_n\) (\(1 \le x_i \le 10^{9}\)) — ваши ставки на исходы.
Можно показать, что если какой-то ответ существует, то всегда существует ответ, удовлетворяющий данным ограничениям.
Если существует несколько подходящих решений, выведите любое из них.
Примечание
В первом наборе входных данных можно распределить монеты следующим образом: \(27\) монет на первый исход, \(41\) монета на второй исход, \(12\) монет на третий исход. Тогда суммарное количество монет, которое будет поставлено на все исходы, равно \(27 + 41 + 12 = 80\) монет. Если первый исход окажется выигрышным, то вы получите обратно \(3 \cdot 27 = 81\) монету, если второй исход окажется выигрышным, то вы получите обратно \(2 \cdot 41 = 82\) монеты, если третий исход окажется выигрышным, то вы получите обратно \(7 \cdot 12 = 84\) монеты. Все эти значения строго больше \(80\).
Во втором наборе входных данных одним из способов является поставить по одной монете на каждый из исходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
3 2 7
2
3 3
5
5 5 5 5 5
6
7 9 3 17 9 13
3
6 3 2
5
9 4 6 8 3
|
27 41 12
1 1
-1
1989 1547 4641 819 1547 1071
-1
8 18 12 9 24
|