题目描述

具身智能部将关键节点配送任务抽象成有限 MDP。每个状态-动作对可能有多个概率转移结果，你需要从给定初始价值出发，做 K 轮同步价值迭代，并在指定查询状态上提取当前最优动作。

同步价值迭代意味着一整轮中所有状态都使用上一轮的价值数组计算，轮末再整体替换。

输入格式

第一行输入三个整数 N A K，表示状态数、动作数和迭代轮数。

第二行输入实数 gamma，表示折扣因子。

第三行输入 N 个实数，表示初始价值 V_1 ... V_N。

第四行先输入整数 T，随后输入 T 个终止状态编号。

第五行输入 A 个实数，表示各动作风险。

接下来按状态 1..N、动作 1..A 的顺序输入转移数据。每个状态-动作对格式为：

legal D
sn_1 p_1 r_1
sn_2 p_2 r_2
...
sn_D p_D r_D

即使 legal = 0，也按输入给出的 D 读取对应转移记录，但该动作不参与选择。

最后输入整数 q，表示查询状态。

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

输出格式

输出一行：

V_q best_action best_q_value

三个数中 V_q 和 best_q_value 保留 6 位小数。

若查询状态为终止状态，或没有合法动作，输出：

0.000000 -1 0.000000

判定规则

每轮迭代中，终止状态的新价值为 0。非终止状态对每个合法动作计算：

Q(s,a) = sum over transitions p * (r + gamma * next_value)

若后继状态为终止状态，则 next_value = 0；否则使用上一轮中的 V[sn]。

状态的新价值取合法动作中 Q(s,a) 的最大值；若并列，取风险更小的动作；若仍并列，取动作编号更小者。若没有合法动作，新价值为 0。

完成 K 轮后，在查询状态上用最终价值数组重新计算各合法动作的 Q 值，并按同样规则输出最佳动作及其动作价值。

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

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 价值迭代会出现不可达节点、终止节点、多个转移价值并列和迭代次数为 0 的情况。
• 更新时应使用上一轮价值同步计算，不能在同一轮中用刚更新的值污染后续节点。
• 即使 legal=0 也必须读取对应转移记录；终止状态每轮价值固定为 0。

样例

输入样例 1

2 2 2
0.9
0 0
1 2
0.1 0.2
1 1 2 1 5
1 1 1 1 1
0 0
0 0
1

输出样例 1

5.500000 2 5.950000

输入样例 2

2 1 1
0.9
5 5
1 2
0.1
1 1 2 1 1
0 0
2

输出样例 2

0.000000 -1 0.000000