Module: Nested Loops


Problem

7 /8


*Mastic

Problem

The store sells mastic in boxes of a kg (type 1), b kg (type 2) and c kg (type 3) ). How to buy exactly N kg of mastic without opening boxes? In how many ways can this be done?
 

Input 
The input string contains four numbers separated by spaces: a , b , c and N .

Imprint 
In the first line you need to print the number K of ways in which you can buy a given amount of mastic (N kg) without opening the boxes. In each of the following K lines, the program should print (separated by spaces) three numbers, ka , kb and kc : the number of boxes of 1, 2 and 3 types for each of the K purchase options. Variants should be output in lexicographic order: Variants with the smallest ka value first, for identical ka – first the variants with the smallest kb value, etc.

 

Examples
# Input Output
1 15 17 21 185 5
0 1 8
1 10 0
3 7 1
5 4 2
7 1 3