Description

你因为对 2016 年 Code Jam 世界总决赛的兴奋，刚刚搬到了纽约。你带来了 $\mathbf{J}$ 件不同的夹克（编号为 $1$ 到 $\mathbf{J}$）、$\mathbf{P}$ 条不同的裤子（编号为 $1$ 到 $\mathbf{P}$）、以及 $\mathbf{S}$ 件不同的衬衫（编号为 $1$ 到 $\mathbf{S}$）。你拥有的衬衫数量不少于裤子的数量，裤子的数量不少于夹克的数量，即满足 $(\mathbf{J} \leqslant \mathbf{P} \leqslant \mathbf{S})$。

每天，你会选择一件夹克、一条裤子和一件衬衫组成当天的穿搭。每天晚上你都会清洗所有衣物，因此每天所有衣物都可以重新使用。

在纽约，时尚警察随时在监视并记录每个人每天的穿着。如果他们发现你穿过完全相同的穿搭两次，你就会立刻被带到五大道的“时尚监狱”进行强制改造；你当然不希望那样！如果他们发现你穿过同一对衣物组合的次数超过 $\mathbf{K}$ 次，你也会立刻被带到时尚监狱。所谓“组合”，是指某一件夹克和某一条裤子的组合、某一件夹克和某一件衬衫的组合，或者某一条裤子和某一件衬衫的组合。例如，在穿搭 (夹克 1, 裤子 2, 衬衫 3) 和 (夹克 1, 裤子 1, 衬衫 3) 这两天中，组合 (夹克 1, 衬衫 3) 出现了两次，而组合 (裤子 1, 衬衫 3) 只出现了一次。

每天你只能穿一套衣服。你能否找出最多可以连续多少天避免被送进时尚监狱，并给出每天的穿搭方案列表？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组一行包含四个整数 $\mathbf{J}, \mathbf{P}, \mathbf{S}, \mathbf{K}$。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 为你能够连续避免被送进时尚监狱的最大天数。随后输出 $\mathrm{y}$ 行，每行三个整数，分别表示某一天的夹克、裤子和衬衫编号（按此顺序）。穿搭顺序可以任意，但不得违反上述时尚警察的规定。

如有多种合法方案，你可以输出任意一种。

4
1 1 1 10
1 2 3 2
1 1 3 2
1 2 3 1

Case #1: 1
1 1 1
Case #2: 4
1 1 2
1 2 3
1 2 1
1 1 1
Case #3: 2
1 1 2
1 1 1
Case #4: 2
1 1 3
1 2 1

Hint

样例解释

样例输出展示了一组可行解，其他答案也可能是正确的。

在第 1 组中，尽管时尚警察对 $\mathbf{K}$ 的限制很宽松（$10$），但你只能组成一种穿搭，因此只能坚持一天。

在第 2 组中，添加任何其他穿搭都会导致你被送进时尚监狱：

• 添加 1 1 3 会导致组合 (夹克 1, 裤子 1) 出现超过 2 次。
• 添加 1 2 2 会导致组合 (夹克 1, 裤子 2) 出现超过 2 次。

在这种情况下，任意 5 套穿搭都必然存在至少一处时尚违规。

注意，单日穿搭中的夹克、裤子、衬衫编号不需要像 $\mathbf{J}, \mathbf{P}, \mathbf{S}$ 那样满足递增关系。

在第 3 组中，你只有一种夹克+裤子的组合，只能反复穿，所以无论衬衫怎么选，都无法组成超过 $\mathbf{K}=2$ 套不同的穿搭。

在第 4 组中，另一组同样规模的最大解为：

1 2 2
1 1 1

限制条件

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{J} \leqslant \mathbf{P} \leqslant \mathbf{S}$。
• $1 \leqslant \mathbf{K} \leqslant 10$。

小数据集（测试集 1 - 可见）

• $\mathbf{S} \leqslant 3$。

大数据集（测试集 2 - 隐藏）

• $\mathbf{S} \leqslant 10$。

翻译由 GPT4.1 完成。