J. Spirit of Cola.
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

After struggling with the bamboo skewers game in Still No Money?, OC, KP, and XW decided to settle things a different way: by drinking cola.

But unfortunately, again, the cola in this world has a spirit protecting it. The spirit has posed a challenge: they must manipulate the cola in three cups to reach a specific amount $$$t$$$.

The three cups have capacities $$$c_1$$$, $$$c_2$$$, and $$$c_3$$$ liters, respectively. Initially, the cups contain $$$w_1$$$, $$$w_2$$$, and $$$w_3$$$ liters of cola. They are allowed to use two types of operations sanctioned by the spirit:

  1. Choose two different cups $$$i$$$ and $$$j$$$, and pour $$$min(w_i, c_j - w_j)$$$ liters of cola from cup $$$i$$$ to $$$j$$$. In other words, pour cola from cup $$$i$$$ to $$$j$$$ until cup $$$j$$$ is full, or cup $$$i$$$ has run out of cola.
  2. Choose one non-empty cup that has the minimum liters of cola and turn it into sugar-free. The spirit hates sugar-free cola and will make the cup empty instantly.

To satisfy the spirit, their goal is to find out a way to make at least one cup have exactly $$$t$$$ liters of cola and minimize the number of operations. But take it easy; if you can prove that there is no way to achieve the goal, just tell the spirit.

Input

The first line contains three integers $$$c_1, c_2, c_3$$$ $$$(1 \leq c_1, c_2, c_3 \leq 300)$$$, denoting the capacities of the three cups.

The second line contains three integers $$$w_1, w_2, w_3$$$ $$$(0 \leq w_1, w_2, w_3 \leq 300, w_i \leq c_i)$$$, denoting the initial amount of cola in the three cups.

The third line contains one integer $$$t$$$ $$$(0 \leq t \leq 300)$$$, denoting the target amount of cola they need to achieve.

Output

If it is possible to achieve the goal, first output one line containing one integer $$$n$$$, denoting the number of operations. Then output $$$n$$$ lines, the $$$i$$$-th line containing three integers, denoting the amount of cola in the three cups after the $$$i$$$-th operation. If there are multiple ways, output any of them.

Otherwise, output $$$-1$$$ instead.

Examples
Input
7 5 2
5 5 0
6
Output
4
3 5 2
3 5 0
1 5 2
6 0 2
Input
2 2 2
2 2 0
1
Output
-1
Input
4 9 9
4 9 0
6
Output
15
0 9 4
4 5 4
0 5 8
4 1 8
3 1 9
3 0 9
0 3 9
4 3 5
0 7 5
4 7 1
2 9 1
2 9 0
0 9 2
4 5 2
0 5 6
Note

For the first sample test case, the initial state is $$$5, 5, 0$$$, and the target amount is $$$6$$$. To achieve the goal, you can perform the following $$$4$$$ operations:

  1. Cup $$$1$$$ $$$\rightarrow$$$ Cup $$$3$$$.
  2. Make Cup $$$3$$$ empty.
  3. Cup $$$1$$$ $$$\rightarrow$$$ Cup $$$3$$$.
  4. Cup $$$2$$$ $$$\rightarrow$$$ Cup $$$1$$$.

These are not the only ways to achieve the goal.