410457: GYM104023 B Recruitment

Cody the Wolf is the coach of a programming competition team. With the new contest season approaching, Cody intends to recruit some new members to the team. He prepares a programming problem for this recruitment:

• There is an expression with $$$n$$$ positive integers and $$$n-1$$$ plus signs $$$a_1+a_2+\dots+a_n$$$. We replace one plus sign $$$+$$$ with a multiplication sign $$$\times$$$ each time and perform $$$n-1$$$ times in total. Please calculate the result of the expression after each replacement.

Cody has generated the standard input and output files for this problem. But he deletes all the standard input files by mistake. Overwhelmed, Cody wonders if he can regenerate the corresponding input files while leaving the output files unchanged.

Formally, given $$$n$$$ integers $$$s_0,s_1,\dots,s_{n-1}$$$, where $$$s_i$$$ indicates the result of the expression after the $$$i$$$-th replacement, you need to construct an initial expression $$$a_1+a_2+\dots+a_n$$$ and determine the position of the plus sign for each replacement such that the result of each replacement matches the given integers $$$s_0,s_1,\dots,s_{n-1}$$$.

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), indicating the number of integers in the expression.

The second line contains $$$n$$$ integers $$$s_0,s_1,\dots,s_{n-1}$$$ ($$$1 \le s_i \le 10^9$$$), where $$$s_i$$$ indicates the result of the expression after the $$$i$$$-th replacement.

If there is no possible solution, output $$$-1$$$ in a single line.

Otherwise, output $$$n$$$ positive integers $$$a_1,a_2,\dots,a_n$$$ in the first line separated by spaces, indicating that the initial expression is $$$a_1+a_2+\dots+a_n$$$. Then output $$$n-1$$$ lines, the $$$i$$$-th of which contains an integer indicating the position of the plus sign for the $$$i$$$-th replacement. You need to make the $$$n-1$$$ integers a permutation of $$$1$$$ to $$$n-1$$$, i.e., each integer from $$$1$$$ to $$$n-1$$$ occurs exactly once.

If there are multiple solutions, output any.

4
13 12 19 60

5 3 4 1
3
1
2

10
10 9 8 7 6 5 4 3 2 1

1 1 1 1 1 1 1 1 1 1 
1
2
3
4
5
6
7
8
9

6
1 1 4 5 1 4

-1

For the first sample:

• The expression after the $$$0$$$th replacement i.e. the initial expression is $$$5+3+4+1=13$$$.
• The expression after the $$$1$$$st replacement is $$$5+3+4\times1=12$$$.
• The expression after the $$$2$$$nd replacement is $$$5\times3+4\times1=19$$$.
• The expression after the $$$3$$$rd replacement is $$$5\times3\times4\times1=60$$$.