Minimizing Towel Service Cost

A software company is planning a software development project that lasts for n days. On day \(i\) the project requires \(n_i\) towels (one per software developer). Each towel must be disinfected after one day of use before it can be re‐used. The company has two disinfection methods available:

• Method \(A\): Disinfection takes \(a\) days and costs \(f_A\) per towel.
• Method \(B\): Disinfection takes \(b\) days and costs \(f_B\) per towel.

Alternatively, the company may purchase a new towel on any day at cost \(f\) (a new towel is already disinfected and available for immediate use).

On each day, the company must decide how many new towels to buy and, for the towels used that day, how many to send for disinfection via method \(A\) or method \(B\) so that they will become available on a future day. In other words, if on day \(i\) a towel is used and is later recycled by method \(A\), it will be available on day \(i+a\) (and by method \(B\) it becomes available on day \(i+b\)).

When a towel is reused via disinfection, the cost for that towel is only the disinfection fee \(f_A\) or \(f_B\) (it does not incur the purchase cost again). Thus, on day 1 a towel can only come by buying at cost \(f\) because no recycled towel is yet available; and on day \(i\) (\(i>1\)) the towel can be obtained either by buying new (cost \(f\)) or by reusing a towel disinfected by method \(A\) (if \(i>a\), cost \(f_A\)) or by method \(B\) (if \(i>b\), cost \(f_B\)).

Your task is to decide, for each day \(1 \le i \le n\):

• How many new towels to purchase on day \(i\).
• How many used towels (from day \(i\)) to send for disinfection by method \(A\) (which will be available on day \(i+a\)).
• How many used towels (from day \(i\)) to send for disinfection by method \(B\) (which will be available on day \(i+b\)).

The goal is to supply the required number of towels each day at the minimum total cost.

Input formulas:

• \(n,\ a,\ b,\ f,\ f_A,\ f_B\) are positive integers.
• \(n_i\) (for \(1 \le i \le n\)) is the demand (number of towels required on day \(i\)).

Note: A towel that is disinfected on day \(i\) will be available on day \(i+a\) if sent for method \(A\), or on day \(i+b\) if sent for method \(B\). Use LaTeX formatting for any formulas.

inputFormat

The first line contains six integers: \(n\), \(a\), \(b\), \(f\), \(f_A\), and \(f_B\).

The second line contains \(n\) integers: \(n_1, n_2, \ldots, n_n\), where \(n_i\) is the number of towels required on day \(i\).

outputFormat

Output three lines:

• The first line contains \(n\) integers representing the number of new towels purchased on each day.
• The second line contains \(n\) integers, where the \(i\)th integer is the number of towels sent for disinfection by method \(A\) on day \(i\) (these will be available on day \(i+a\)).
• The third line contains \(n\) integers, where the \(i\)th integer is the number of towels sent for disinfection by method \(B\) on day \(i\) (these will be available on day \(i+b\)).

You may assume that if a towel is obtained via recycling, it uses only the disinfection cost (\(f_A\) or \(f_B\)).

sample

5 2 3 15 1 2
5 5 5 5 5

5 5 0 0 0
5 5 5 0 0
0 0 0 0 0

</p>