Fashion Police (Large)

You are so excited about the 2016 Code Jam World Finals that you just moved to New York. You have brought along $J$ different jackets (numbered 1 through $J$), $P$ different pairs of pants (numbered 1 through $P$), and $S$ different shirts (numbered 1 through $S$). You have at least as many shirts as pairs of pants, and at least as many pairs of pants as jackets. ($J \le P \le S$.)

Every day, you pick one jacket, one pair of pants, and one shirt to wear as an outfit. You wash all of your garments every night, so all of your garments are available to use each day.

In New York, the Fashion Police officers are always watching and keeping track of what everyone wears every day. If they find out that you have worn the exact same outfit twice, you will immediately be taken to the Fashion Jail on 5th Avenue for a mandatory makeover; you definitely want to avoid that! You will also immediately be taken to Fashion Jail if they find out that you have worn the same two-garment combination more than $K$ times in total. A combination is a particular jacket worn with a particular pair of pants, a particular jacket worn with a particular shirt, or a particular pair of pants worn with a particular shirt. For example, in the set of outfits (jacket 1, pants 2, shirt 3) and (jacket 1, pants 1, shirt 3), the combination (jacket 1, shirt 3) appears twice, whereas the combination (pants 1, shirt 3) appears only once.

You wear one outfit per day. Find the largest possible number of days you can avoid being taken to Fashion Jail, and produce a list of outfits to use each day.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow; each consists of one line with four integers $J$, $P$, $S$, and $K$.

Limits

• $1 \le T \le 100$
• $1 \le J \le P \le S$
• $1 \le K \le 10$
• $S \le 10$

For each test case, first output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of days you can avoid being taken to Fashion Jail. Then output y more lines, each with three integers: the numbers of the jacket, pants, and shirt (in that order) for one day's outfit.

To make the answer unique, the outfit $(a, b, c)$ (jacket $a$, pants $b$, shirt $c$) is in the list exactly when

$(c - a - b + 1) \bmod S < \min(K, S)$

where the result of $\bmod$ is taken in the range $0$ to $S - 1$. Output every outfit that meets this condition, sorted in ascending lexicographic order (compare the jacket number, then the pants number, then the shirt number). The list built by this rule is a longest list that keeps you out of Fashion Jail.

In Case #1, even though the Fashion Police officers have set a lenient value of $K = 10$, you can form only one outfit, so you can avoid Fashion Jail for only one day.

In Case #2, adding any other outfit would send you to Fashion Jail:

• Adding 1 1 3 would use the combination (jacket 1, pants 1) more than 2 times.
• Adding 1 2 1 would use the combination (jacket 1, pants 2) more than 2 times.

In this case, any set of 5 outfits includes at least one fashion violation.

Unlike $J$, $P$, and $S$, the numbers of the jacket, pants, and shirt within one outfit do not have to be in nondecreasing order.

In Case #3, you have only one jacket and pants combination, which you must keep reusing, so no matter which shirts you wear, you cannot form more than $K = 2$ different outfits.

In Case #4, several maximum sets of outfits exist, but the output rule requires 1 1 1 and 1 2 2.