#215390. [NHSPC 2025] Chomp!

是一個經典的兩人遊戲。起始時有一片由 塊大小為 的小塊巧克力連為一片的巧克力，形狀如 的二維陣列（其中 為列， 為行），而最左下角的那一小塊非常苦澀，大家都想避開。遊戲的玩法為輪流拿走巧克力小塊，方式是先從剩下來的巧克力挑一小塊，並把其右上方（含正上方及正右方）所有小塊同時拿掉。到最後誰拿到最左下角的那一小塊便輸了。

例如起始時有 的一片巧克力：

:::align{center} :::

若玩家一選擇了 那一小塊，則連帶 的那些小塊也會被拿掉：

:::align{center} :::

接著由玩家二從剩下的巧克力塊選擇。若玩家二此時選擇了 那一小塊，則連帶 的那些小塊也會被拿掉：

:::align{center} :::

按照以上規則，我們不難證明，在遊戲中所出現的任何情形，如從左至右輸出每一行 (column) 的巧克力小塊數，其結果必為一單調遞減 (monotonic decreasing) 數列，且對應此數列之形狀唯一。如上述範例的最終狀態，其可以數列 表示。

在此題目中，我們針對 大小巧克力的 遊戲中出現的各種情況進行分析，目的是計算在當前的情況下，先行者是否有獲勝的走法。我們假設遊戲雙方皆絕頂聰明，會採取最好的遊玩策略來讓自己獲勝。若先行者能獲勝，我們輸出在目前情況下有多少種可以獲勝的第一步選擇，並把這些選擇枚舉出來；反之，則輸出 。這裡，我們將下面數上來第 列、左邊數過來第 行的小塊巧克力編號為 ，滿足左下角為 ，右上角為 。

• 代表總共有 筆詢問。
• 代表第 筆詢問的巧克力總行數。
• 代表第 筆詢問的狀態為從左至右先有 行為 小塊巧克力，接著有 行為 小塊巧克力，再有 行為 小塊巧克力。

• 代表在第 筆詢問的狀態下，先行者可以獲勝的第一步選擇數。若先行者無法獲勝，則 。
• 代表第 筆詢問中，第 個可以作為先行者獲勝的第一步選擇的小塊巧克力編號。若 ，請依 值小到大排序編號，若 值相同則依 值小到大排序編號。

样例输入 1

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

样例输出 1

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

样例输入 2

1
100 67 22 11

样例输出 2

3
1 100 2 59 3 18

測資限制

• 。
• 。
• 。
• 。
• 輸入的數皆為整數。

評分說明

本題共有三組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。