P15239 [NHSPC 2025] Chomp!

$\textit{Chomp!}$ 是一个经典的两人游戏。起始时有一片由 $mn$ 块大小为 $1 \times 1$ 的小块巧克力连为一片的巧克力，形状如 $m \times n$ 的二维数组（其中 $m$ 为行，$n$ 为列），而最左下角的那一小块非常苦涩，大家都想避开。游戏的玩法为轮流拿走巧克力小块，方式是先从剩下来的巧克力挑一小块，并把其右上方（含正上方及正右方）所有小块同时拿掉。到最后谁拿到最左下角的那一小块便输了。 例如起始时有 $3 \times 4$ 的一片巧克力： :::align{center}  ::: 若玩家一选择了 $X$ 那一小块，则连带 $Y$ 的那些小块也会被拿掉： :::align{center}  ::: 接着由玩家二从剩下的巧克力块选择。若玩家二此时选择了 $W$ 那一小块，则连带 $Z$ 的那些小块也会被拿掉： :::align{center}  ::: 按照以上规则，我们不难证明，在游戏中所出现的任何情形，如从左至右输出每一列 (column) 的巧克力小块数，其结果必为一单调递减 (monotonic decreasing) 数列，且对应此数列之形状唯一。如上例的最终状态，其可以数列 $(3, 1, 0, 0)$ 表示。 在此题目中，我们针对 $3 \times n$ 大小巧克力的 $\textit{Chomp!}$ 游戏中出现的各种情况进行分析，目的是计算在当前的情况下，先行者是否有获胜的走法。我们假设游戏双方皆绝顶聪明，会采取最好的游玩策略来让自己获胜。若先行者能获胜，我们输出在目前情况下有多少种可以获胜的第一步选择，并把这些选择枚举出来；反之，则输出 $0$。这里，我们将下面数上来第 $i$ 行、左边数过来第 $j$ 列的小块巧克力编号为 $(i, j)$，满足左下角为 $(1, 1)$，右上角为 $(3, n)$。

$$ \begin{aligned} &t \\ &n_1 \; p_1 \; q_1 \; r_1 \\ &\vdots \\ &n_t \; p_t \; q_t \; r_t \end{aligned} $$ * $t$ 代表总共有 $t$ 笔询问。 * $n_i$ 代表第 $i$ 笔询问的巧克力总列数。 * $p_i, q_i, r_i$ 代表第 $i$ 笔询问的状态为从左至右先有 $p_i$ 列为 $3$ 小块巧克力，接着有 $q_i$ 列为 $2$ 小块巧克力，再有 $r_i$ 列为 $1$ 小块巧克力。

$$ \begin{aligned} &c_1 \\ &x_{1,1} \; y_{1,1} \; \dots \; x_{1,c_{1}} \; y_{1,c_{1}} \\ &\vdots \\ &c_t \\ &x_{t,1} \; y_{t,1} \; \dots \; x_{t,c_{t}} \; y_{t,c_{t}} \end{aligned} $$ * $c_i$ 代表在第 $i$ 笔询问的状态下，先行者可以获胜的第一步选择数。若先行者无法获胜，则 $c_i = 0$。 * $x_{i,j}, y_{i,j}$ 代表第 $i$ 笔询问中，第 $j$ 个可以作为先行者获胜的第一步选择的小块巧克力编号。若 $c_i > 1$，请依 $x$ 值小到大排序编号，若 $x$ 值相同则依 $y$ 值小到大排序编号。

### 数据限制 * $1 \le t \le 1000$。 * $1 \le n_i \le 500$。 * $0 \le p_i, q_i, r_i \le n_i$。 * $1 \le p_i + q_i + r_i \le n_i$。 * 输入的数皆为整数。 ### 评分说明 本题共有三组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 20 | $t = 1$，$p_i = 0$。 | | 2 | 37 | $1 \le n_i \le 50$。 | | 3 | 43 | 无额外限制。 |