G. Hourglass
time limit per test
0.5 seconds
memory limit per test
24 megabytes
input
standard input
output
standard output

In the middle ages, artisans used a hourglass for measuring time. As such devices were quite rare and expensive, not every master had a set of them that made it possible to measure any time interval. Artisans were very inventive, and managed to produce very complex measurements with the help of minimum options (choice of devices). For example, with the help of 3-minute and 5-minute devices any number of minutes (greater than 4) could be calculated. And can you surpass our ancestors?

You have $$$n$$$ (up to 4) hourglasses numbered $$$1$$$, $$$2$$$, ..., $$$n$$$, the sand in which is poured during $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ (up to 20) minutes, respectively. Compile a program that will find a way to measure out $$$k$$$ minutes with the help of this device. Note that:

  • any hourglass can be turned over only at the very beginning of measurements, or at the moment when one of the device has run out of sand;
  • at such a moment, you can turn over any number of devices (hourglasses) at the same time. The hourglass is turned over instantly;
  • it is forbidden to put the clock onto one side (to stop the time);
  • the measured interval of $$$k$$$ minutes starts from the very first turning of any device;
  • the measured interval of $$$k$$$ minutes should end at the moment when any device has run out of sand.

For example, let us have a device for 3 and 5-minute duration. Let's show how they can be used to measure 7 minutes:

  • 0 minute. At the same time, we turn both the devices for 3 and 5-minute duration.
  • 3 minutes. The 3 minute hourglass is empty and the 5 minute device has sand for 2 minutes more. Turn the device over for 3 minutes.
  • 5 minutes. The 5 minute device is empty, in the 3 minute device there is sand still for 1 minute from above, and for 2 minutes from below. Turn the hourglass over for 3 minutes.
  • 7 minutes. The hourglass for 3 minutes is empty. The specified interval is measured.
Input

The first line of input contains the integer $$$n$$$ ($$$1 \leq n \leq 4$$$) — the number of hourglasses. The second line contains integers $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ ($$$1 \leq t_1 \lt t_2 \lt \ldots \lt t_n \leq 20$$$) separated by spaces — hourglass denominations. The third line contains the integer $$$k$$$ ($$$1 \leq k \leq 1440$$$) — the time interval to be measured.

Output

The first line of the output contains $$$-1$$$ if the time interval $$$k$$$ cannot be measured.

Otherwise, it contains an integer $$$r$$$ — the number of time moments ($$$1 \leq r \leq k$$$) at which the hourglass is turned over. This is followed by $$$r$$$ lines describing the moments of turning the clock over.

Each such line begins with the number $$$t_i$$$ — the number of minutes from the start of the countdown, up to the moment of this inversion. Next, a space is followed by the number $$$m_i$$$ ($$$0 \leq m_i \leq n$$$) — the number of hourglasses flipped at the time of $$$t_i$$$. Further, after a space, the numbers of the turned over hourglasses are specified.

The lines should be displayed in the increasing order of time: $$$t_i \gt t_{i-1}$$$. At the moment of time specified as $$$t_i$$$, at least, one hourglass should run out of sand.

The first line should contain a description of the initial time ($$$t_1=0$$$). The last line must contain the time point $$$k$$$ and 0 of the hourglasses that are being flipped. Lines with time specification $$$t_i \gt k$$$ can't be displayed. Lines with time specification $$$m_i = 0$$$ are allowed and are not considered a mistake.

Examples
Input
2
3 5
7
Output
4
0 2 1 2
3 1 1
5 1 1
7 0
Input
2
3 5
4
Output
-1
Input
2
7 9
13
Output
5
0 2 1 2
7 1 1
9 2 1 2
11 1 2
13 0