题目描述

具身智能部把一次投放任务拆成若干个可复用模板：有的模板负责取到物体，有的负责移动到投放区，有的会清除临时状态。每个模板都有前置状态、增加状态和删除状态。给定初始状态和目标状态，你需要补出最短任务链。

状态用整数位掩码表示。若当前状态 st 满足 (st & pre) == pre，则可以执行该模板，得到新状态：

(st & ~delete) | add

若新状态与原状态相同，则这次执行不扩展搜索。目标达成条件为 (st & goal) == goal。请按模板编号升序进行 BFS，因此第一次到达目标时得到的就是步数最少、并在该搜索规则下最靠前的任务链。

输入格式

第一行输入 s task_count goal，其中 s 表示状态位数，task_count 表示模板数量，goal 为目标位掩码。第二行输入初始状态 start。

接下来 task_count 行，每行输入：

tid pre add delete cost

其中 tid 为模板编号。cost 只作为输入字段保留，本题搜索不使用它。

输出格式

若能达成目标，输出最短链长度，后接按执行顺序排列的模板编号：

len tid1 tid2 ...

若初始状态已经达成目标，只输出 0。若无法达成目标，输出：

TASK_UNREACHABLE

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 任务链可能已经完整，也可能缺少多个必要步骤；补全时要保留原有动作顺序约束。
• 若目标不可抓取、不可投放或中途资源不足，应按题面输出失败而不是生成部分计划。
• 初始状态已满足目标时只输出 0；不改变状态的模板不能扩展 BFS，模板按 tid 升序尝试。

样例

输入样例 1

8 7 127
1
1 1 2 0 1
2 3 4 0 1
3 5 8 0 1
4 9 16 0 1
5 16 32 0 1
6 32 64 0 1
7 64 128 0 1

输出样例 1

6 1 2 3 4 5 6

输入样例 2

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

输出样例 2

0