Math Homework

Interview

Time limit1sMemory limit1024 MB

Summary

Given the leg counts b, d, c of three animal types and a total of l legs, list every count triple whose legs add up to l, or print impossible.

Level: Easy2 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

Since entering 2nd grade, Theta has had daily math homework sheets. The problems on her worksheet usually go like this:

There is a certain number of birds, dogs, and cats on a farm. Together they have $14$ legs. How many birds, dogs, and cats could there be? Write down as many answers as you can!

It is always the same problem, just written in different ways: sometimes with horses, cows, sheep, goats, chickens, beetles, or even spiders (but never with snakes or fishes!)

Can you write a program to double-check Theta's answers?

Input

The input consists of a single line with 4 integers $b$ , $d$ , $c$ , and $l$ . $b$ , $d$ , and $c$ are the numbers of legs the first, second, and third type of animal has. You are given that $0 < b, c, d \le 100$ , because some farm animals in these problems may be centipedes. The total number of legs is $l$ ( $0 \le l \le 250$ ).

Output

Output all possible answers, each on a separate line, in lexicographical order: sorted by the number of the first animal, with ties broken by the second and then the third animal. Separate the number of the first, second, and third animal with spaces. If there are no possible solutions, output impossible on a single line.

Examples3

Example 1

Input

2 4 4 14

Expected output

Example 2
Input
```
100 80 60 240
```
Expected output
```
0 0 4
0 3 0
1 1 1
```
Example 3
Input
```
2 4 6 9
```
Expected output
```
impossible
```