C. Заработать на ставках
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам было предложено сыграть в игру. В данной игре возможно $$$n$$$ исходов, на каждый из которых вы должны поставить некоторое целое количество монет. В случае, если $$$i$$$-й исход окажется выигрышным, вы получите обратно количество монет в размере вашей ставки на этот исход, умноженной на $$$k_i$$$. Обратите внимание, что ровно один из $$$n$$$ исходов окажется выигрышным.

Ваша задача — сказать, как распределить монеты так, чтобы при любом выигрышном исходе выйти в плюс. Более формально, суммарное количество монет, которое вы поставили на все исходы, должно быть строго меньше числа монет, полученных обратно при каждом возможном выигрышном исходе.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество исходов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$k_1,k_2,\ldots,k_n$$$ ($$$2 \le k_i \le 20$$$) — во сколько раз умножается количество монет, если $$$i$$$-й исход оказывается выигрышным.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$-1$$$, если требуемого способа распределить монеты не существует. Иначе выведите $$$n$$$ целых чисел $$$x_1, x_2,\ldots, x_n$$$ ($$$1 \le x_i \le 10^{9}$$$) — ваши ставки на исходы.

Можно показать, что если какой-то ответ существует, то всегда существует ответ, удовлетворяющий данным ограничениям.

Если существует несколько подходящих решений, выведите любое из них.

Пример
Входные данные
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
Примечание

В первом наборе входных данных можно распределить монеты следующим образом: $$$27$$$ монет на первый исход, $$$41$$$ монета на второй исход, $$$12$$$ монет на третий исход. Тогда суммарное количество монет, которое будет поставлено на все исходы, равно $$$27 + 41 + 12 = 80$$$ монет. Если первый исход окажется выигрышным, то вы получите обратно $$$3 \cdot 27 = 81$$$ монету, если второй исход окажется выигрышным, то вы получите обратно $$$2 \cdot 41 = 82$$$ монеты, если третий исход окажется выигрышным, то вы получите обратно $$$7 \cdot 12 = 84$$$ монеты. Все эти значения строго больше $$$80$$$.

Во втором наборе входных данных одним из способов является поставить по одной монете на каждый из исходов.