405914: GYM102156 E Permutasino

At last, the famous spy and secret agent James Bond succeeded in finding his current nemesis, Dr. Zlo. They met at the roulette table of the casino Permutasino, and now 007 tries to guess the latest evil plan of his vicious enemy.

The roulette table consists of $$$n!$$$ cells containing all possible permutations of integers between $$$1$$$ and $$$n$$$. Betting process in this roulette is rather unusual: player puts no more than $$$n$$$ bets on some of the cells. Each bet is a non-negative number $$$b_{\pi}$$$ where $$$\pi$$$ denotes the permutation it corresponds to. The sum of all bets should be equal to $$$1$$$.

After bets are made, the roulette mechanism picks a random permutation from the distribution defined by the numbers $$$b_{\pi}$$$. Formally, the permutation $$$\pi$$$ will be chosen with probability $$$b_{\pi}$$$ if there is a bet on permutation $$$\pi$$$, or with probability $$$0$$$ otherwise.

In order to beat Dr. Zlo in this mind battle and persuade him to disclose his evil plan, 007 has to make bets in such way that the expected value of the resulting permutation is a vector $$$(x_1, x_2, \ldots, x_n)$$$. Consider expected value of a random permutation of length $$$n$$$ to be defined as a vector of length $$$n$$$, where $$$i$$$-th element is the expected value of the $$$i$$$-th element of the random permutation.

Help James Bond to make appropriate bets, or determine that it is not possible and he has to save the world by using different means (like shooting everyone and blasting every building on his way) this time.

The first line of input contains a single integer $$$n$$$, the length of the permutations appearing at the roulette table ($$$1 \leq n \leq 500$$$).

The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq n$$$), the desired expected value of the resulting permutation.

If there is no way to obtain the vector $$$(x_1, x_2, \ldots, x_n)$$$ as the expected value of the game result, print $$$-1$$$.

Otherwise, in the first line, print $$$k$$$ ($$$1 \leq k \leq n$$$), the number of bets to be made by James Bond.

In the $$$i$$$-th of the following $$$k$$$ lines, print the bet value $$$b_{\pi_{i}}$$$ ($$$0 \leq b_{\pi_i} \leq 1$$$) and $$$n$$$ integers $$$\pi_{i,1}, \pi_{i,2}, \ldots, \pi_{i,n}$$$ ($$$1 \leq \pi_{i,j} \leq n$$$, all $$$\pi_{i,j}$$$ over all $$$1 \leq j \leq n$$$ are distinct), defining the corresponding permutation $$$\pi_{i}$$$.

The sum $$$b_{\pi_1} + b_{\pi_2} + \ldots + b_{\pi_n}$$$ should be equal to $$$1$$$ with an absolute error of no more than $$$10^{-6}$$$. The maximum value of $$$\left|b_{\pi_1} \pi_{1,j} + b_{\pi_2} \pi_{2,j} + \ldots + b_{\pi_k} \pi_{k,j} - x_j\right|$$$ over all $$$1 \leq j \leq n$$$ should not exceed $$$10^{-2}$$$. All calculations to verify these facts will be performed using the double precision floating point data type.

If there are several possible answers, print any one of them.

4
2 2 3 3

3
0.5000000000 1 2 3 4
0.1666666667 1 4 3 2
0.3333333333 4 1 3 2

2
1 1

-1

In the first sample test, the expected value of the resulting permutation is $$$$$$\left( \frac{1}{2} \cdot 1 + \frac{1}{6} \cdot 1 + \frac{1}{3} \cdot 4,~~ \frac{1}{2} \cdot 2 + \frac{1}{6} \cdot 4 + \frac{1}{3} \cdot 1,~~ \frac{1}{2} \cdot 3 + \frac{1}{6} \cdot 3 + \frac{1}{3} \cdot 3,~~ \frac{1}{2} \cdot 4 + \frac{1}{6} \cdot 2 + \frac{1}{3} \cdot 2\right) = (2, 2, 3, 3)\text{.}$$$$$$