暂无测试数据。

在遥远的的未来，人类建立了宇宙级文明。

星际交通部门把星球编号为 $1,2,...,n$，有 $m$ 对 单向通行 的虫洞，第 $i$ 对虫洞的入口在星球 $a_i$，出口在星球 $b_i$。

有 $k$ 种矿物，第 $i$ 种矿物的价值为 $w_i$，矿物的价值和矿物的数量无关，只取决于你是否拥有这种矿物。

不同星球上矿石的种类不同，用一个 $01$ 序列来描述星球 $i$ 上的矿石种类集合，如果这个序列从左往右数的第 $i$ 数字是 $1$ 说明星球上存在着第 $i$ 种矿物，为数字 $0$ 说明星球上不存在第 $i$ 种矿物。

矿物买卖商人小明有一艘用来开采矿物的飞船，他收到了 $q$ 份委托，每个委托用六元组 $(y_i,s_i,t_i,p_i,c_i,l_i)$ 来描述，表示委托人希望小明在第 $y_i$ 年的年初出发，从星球 $s_i$ 开始采矿，到 $t_i$ 星球结束采矿，总共历时 $l_i$ 年，途中只能通过虫洞来移动，必须选择最优路线，使得所开采的矿物的收益最大，此次旅途的成本为 $c_i$，收益为所采集到的矿物的价值之和 (你的收益只取决于每种矿物拥有与否)，这次旅程持续 $l_i$ 年，还要承担 $p_i$ 的风险，因为种种不可控因素飞船有 $p_i$ 的概率会在途中损毁，损毁后将无法获得此次采矿的收益，而且以后飞船将 再也无法 出行。

注意，每份委托都有对应的时间区间，飞船不能同时执行多个任务，所以时间冲突的两份委托不可能同时接受。

请你来帮帮小明，他应该选择接受哪些委托，使得他所得总收益的数学期望值最大？

注意常数因子对程序效率带来的影响。

输入格式

第一行 $4$ 个整数，$n,m,k,q$。

接下来 $n$ 行，每行一个长度为 $k$ 的 $01$串，意义如题目中所述。

接下来 $m$ 行，每行一对整数 $a_i,b_i$，描述了一对虫洞。

接下来 $k$ 行，每行一个整数表示 $w_i$。

接下来 $q$ 行，每行 $6$ 个数 $y_i,s_i,t_i,p_i,c_i,l_i$，其中除 $p_i$ 之外都是正整数，而 $p_i$ 是一个在闭区间 $[0,1]$ 内的浮点数，有最多三个小数位。

输入保证至少存在一条从 $s_i$ 到 $t_i$ 的路径。

输出格式

一个数字，表示最大期望获利，你的答案和标准答案的误差不超过$10^{-6}$即视为正确。

数据规模

对于全部的数据，$1\leq s_i,t_i,a_i,b_i\leq n$，$1\leq y_i,l_i\leq 10^9$，$1\leq c_i,w_i\leq 10^3$。

4 4 2 2
11
01
10
01
1 2
2 3
3 4
4 2
3
4
10 1 2 0.01 5 10
20 4 4 0.7 3 7

1.93