题目描述

$\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$ 值小到大排序編號。

4
1 0 0 1
10 1 0 9
3 1 2 0
3 1 1 1

0
1
1 4
2
1 3 2 2
3
1 3 2 2 3 1

1
100 67 22 11

3
1 100 2 59 3 18

提示

測資限制

• $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	無額外限制。