题目描述

具身智能部把地面巡检机器人面前的若干移动方案整理成一个小型 MDP。每个动作会以若干概率转移到后继区域，并产生对应的即时奖励。你需要筛掉不可执行动作，计算每个合法动作的期望即时奖励和最可能到达的区域，再给出本轮最优动作。

对同一个动作，若多个转移记录指向同一后继区域，它们的概率需要累加，用于判断“最可能到达的区域”；期望奖励仍按每条记录的 概率 × 奖励 求和。

输入格式

第一行输入三个整数 N s A，表示状态总数、当前状态编号和动作数。

接下来对每个动作输入一组数据：

aid legal risk K
sn_1 p_1 r_1
sn_2 p_2 r_2
...
sn_K p_K r_K

其中 aid 为动作编号，legal 表示动作是否合法，risk 为风险值，K 为该动作的转移记录数；每条转移记录表示以概率 p_i 到达状态 sn_i 并获得即时奖励 r_i。这些字段在输入中连续给出，可能位于同一行。

最后输入 T，随后输入 T 个终止状态编号。

状态和动作编号均为 1-based。

输出格式

若当前状态 s 是终止状态，输出：

TERMINAL

若没有任何合法动作，输出：

-1

否则，先按动作编号从小到大输出每个合法动作：

aid expected_reward most_likely_state

其中 expected_reward 保留 6 位小数。

最后输出一行：

BEST aid most_likely_state

判定规则

合法动作的期望即时奖励为所有转移记录的 p_i * r_i 之和。

most_likely_state 取累加概率最大的后继状态；若并列，取编号最小的状态。

最优动作选择期望奖励最大的合法动作；若并列，取风险更小者；若仍并列，取动作编号更小者。

使用标准输出比较，所有浮点数保留 6 位小数。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 移动决策会覆盖禁行区、能量不足、目标区域相同和多个候选并列的情况。
• 当预算或风险刚好等于阈值时，请按题面包含或严格不等的规定判断，不要统一写成 < 或 <=。
• 当前状态若为终止状态直接输出 TERMINAL；无合法动作输出 -1，最大概率后继并列取状态编号小者。

样例

输入样例 1

3 1 2
1 1 0.2 2 2 0.7 5 3 0.3 -10
2 1 0.1 1 1 1.0 1
0

输出样例 1

1 0.500000 2
2 1.000000 1
BEST 2 1

输入样例 2

2 1 2
1 0 0.1 1 2 1 5
2 0 0.2 1 1 1 3
0

输出样例 2

-1