题目描述

一座设施中有 $N$ 个房间，房间之间由无向走廊连接。你从房间 start 出发，希望尽快到达房间 finish。通过任意一条走廊都恰好需要 $1$ 秒。

设施中还有若干名特工。第 $i$ 名特工从 agentStart[i] 出发，前往 agentTarget[i]。所有人同时开始行动。每名特工一定选择一条从起点到目标的最短路；如果最短路不止一条，他会在所有最短路中等概率随机选择一条。一旦到达目标房间，特工会一直停留在那里。你知道各特工的起点和目标，但在移动过程中无法观察他们实际选择了哪条路。

你的策略如下：每一秒都必须选择一条仍能让你以最短时间到达 finish 的走廊；如果有多个这样的选择，则选择使从当前时刻开始最终被抓概率最小的那一条。到达 finish 后你立即离开，但在刚到达该房间的那一刻仍可能被抓。

以下任一情况都会被某名特工抓住：

• 你和特工在同一秒经过同一条走廊，无论方向相同还是相反；
• 你和特工在同一时刻位于同一个房间。

请输出按照上述最优策略行动时，你最终被至少一名特工抓住的概率。

输入格式

第一行输入两个整数 start finish。

第二行输入两个整数 $N,M$。本题数据保证 $N=M$。

接下来 $N$ 行，每行一个长度为 $N$ 的 01 字符串。第 $i$ 行第 $j$ 个字符为 1 表示房间 $i$ 与房间 $j$ 之间有走廊，否则为 0。

接下来一行输入整数 $A$，下一行输入 $A$ 个整数，表示所有 agentStart。

再下一行输入整数 $B$，最后一行输入 $B$ 个整数，表示所有 agentTarget。保证 $A=B$，且下标一一对应同一名特工。

输出格式

输出一个实数，表示最终被抓住的概率。答案的绝对误差或相对误差不超过 $10^{-9}$。

数据范围

• $2\le N\le 25$；
• 图为无向连通图，邻接矩阵关于主对角线对称，主对角线均为 0；
• $0\le start,finish<N$ 且二者不同；
• $1\le A=B\le 10$；
• 每名特工的起点与目标不同；
• 没有特工与玩家从同一房间出发。

样例

输入

0 3
6 6
010000
101011
010111
001000
011000
011000
1
4
1
5

输出

0.5