背景

JHB 成功捉获了一个入侵者，从他的口中JHB 了解到WZland 的中心存在一个古代遗址，这个遗址内部存在一个神秘的物件，获得这个物件之后可以拥有不可思议的力量……

问题描述

JHB第一时间就将这个消息透露给WZland的国王，但国王对这件事情不怎么关心，他鸟都没鸟JHB就去干其他事情去了。

没办法JHB就将这个消息告诉了WZOI小组的其他成员，他们决定一起去找寻找这个神秘的遗址。WZOI的小组成员了解到古代遗址在一个十分隐秘的地方，他们不能通过开车的方式到达那里，他们只能通过巨大的传送网络到达古代遗址所在的地方。

这个传送网络中存在N个传送站点，简单地标号为1，2，…，N。每个传送点有一个传送门，两个不同的传送点可通过传送门相互到达，但并不是所有的传送点都可以通过传送门直接相互到达。这个传送网络中存在M个传送通道，每个传送通道可以用两个互不相同的整数A和B来描述，表示传送点A和传送点B可直通过一次传送而相互可达。

ZOI的人了解到他们现在处于传送点S，而古代遗址处于传送点T，在点S处他们的传送速度为V。这个传送网络还有一个神奇之处，它的每一个站点拥有一个参数Ci，如果在传送点a的传送速度为Va，传送点a的参数为Ca，传送点b的参数为Cb，传送点b和传送点a可以直接传送。那么在传送点b的速度为Vb=Va*2^(Cb-Ca)，而通过这个传送通道的时间为1/Va.

WZOI的成员们想知道他们怎样才能用最少的时间到达目的地。

输入格式

输入数据第1行包含三个整数N,M,V，分别表示传送站点的数目，传送通道的数目，以及初始速度；

第2行包含N个整数，C1,C2,…,CN，其中Ci(1≤i≤N)表示第i个传送通道的参数；

第3行到第M+3行，每行两个整数A,B(1≤A,B≤N，A≠B)，表示传送点A和传送点B存在传送通道；

第M+4行，包含两个整数S，T(1≤S,T≤N，S≠T)，分别表示出发点和目的地。

输出格式

输出数据只有一行，包含一个数T，表示WZOI 的成员最少需要花多少时间能到达目的地。

注意T 可能是一个实数，你只需要将它保留一位小数输出即可。

样例输入输出

Sample #1vestige.in

3 3 1
1 2 3
1 2
2 3
1 3
1 3

vestige.out

1.0

vestige.in

4 5 2
3 2 4 1
1 3
1 4
1 2
3 4
2 3
1 4

vestige.out

0.5

数据规模

对于30%的数据，N≤1000，M≤10000；

对于50%的数据，N≤20000，M≤200000；

对于100%的数据，N≤100000，M≤200000；

对于100%的数据，Ci∈[-20,20]，V≤100000.输入数据保证存在一条路径从S到达T。