F. Bickford fuse
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are quite many puzzles where one should measure the needed time interval with the help of unevenly burning Bickford (fire-conducting) fuses. For example, with a rope that entirely burns out for $$$1$$$ minute, one can measure $$$30$$$ seconds – for that, the rope should be set on fire from both sides. One can measure $$$45$$$ seconds with two such ropes (for $$$1$$$ minute each) – the first rope should be set on fire from both sides and the second only from one side – at the moment when the first rope burns down ($$$30$$$ seconds), one needs to set on fire the other end of the second rope: it will burn to the end in $$$45$$$ seconds.

Consider a more general problem: let us have $$$ n $$$ Bickford fuses with burning durations $$$ d_1, d_2, \dots, d_n $$$ . Is it possible to use them to measure the time interval $$$Time$$$, if it is allowed to set on fire these ropes either at the initial moment of time or at the moment of burning out of some other rope?

Write a program that solves this problem or informs that there is no solution. If there are several possible solutions, any of them is considered correct.

Input

The first line contains one integer – the amount of Bickford fuses $$$ n $$$ $$$( 1 \leq n \leq 6 )$$$.

The second line contains $$$ n $$$ integers $$$ d_1, d_2, \dots, d_n $$$ $$$( 1 \leq d_i \leq 120) $$$ separated by spaces – burning duration of fuses in seconds.

The third line contains integer $$$ Time $$$ $$$( 1 \leq Time \leq 600 )$$$ – an interval in seconds that should be measured.

Output

The first line contains the amount of used fuses $$$ k $$$ $$$( 1 \leq k \leq n )$$$, or $$$-1$$$ if the solution does not exist.

If the solution exists, there are $$$k$$$ number of lines, each containing one fractional number and three integers separated by spaces: $$$ t_{off}$$$ $$$ num $$$ $$$ t_1 $$$ $$$ t_2 $$$. Each such quad describes the moment of burning down of the fuse $$$ t_{off} $$$ (with precision to $$$ 10^{-10} $$$ sec); the number of the fuse $$$ num $$$, which sides were set on fire in moments of time with indexes $$$t_1$$$ and $$$t_2$$$. Lines should be in ascending order $$$ t_{off} $$$.

Fuses are numbered with numbers $$$ 1, 2, \dots, n $$$ in order of their appearance in input data.

Time moments are numbered with numbers $$$ 1, \dots, k $$$ in order of their appearance in output data. Index $$$0$$$ is given to the begging point of time, and index $$$-1$$$ is used instead of $$$ t_2 $$$ if the second side of the fuse is not set on fire.

If there are multiple solutions, print any of them.

Examples
Input
2
60 60
45
Output
2
30 1 0 0
45 2 0 1
Input
1
10
4
Output
-1