测试数据来自 system/1050

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

一切都准备好了，贺卡和礼物，还有圣诞老人的微笑。圣诞老人用大红袋子把这些贺卡和礼物装好。放在雪车的后端。挥手和小精灵们告别。

现在，圣诞老人要去钻烟囱送礼物去咯！可是，又有一个同写贺卡一样的问题出现了。世界上那么多孩子，那么多贺卡和礼物。难道圣诞老人一个人凭着这一个圣诞夜就能够把所有的礼物都送到孩子们的手上吗？告诉你吧：Impossible！所以……圣诞老人只会去挑一些孩子，把礼物送给他们。然后马上返回到北极圣诞区，去参加圣诞夜钟声敲响时刻的极光表演。所以呢……
大家知道，地球是个球的……地球是离太阳第三远的行星，绕太阳转动的恒星周期为365.26天，距离大约是1.49亿平方公里(9,296万英里），自转一周的周期为23小时56.07分，半径为6,374千米，质量是29.11×10^24千克……
现在，世界上一共有n个孩子，住在同一个星球——地球。也就是说他们住在同一个半径为6374千米的球体上。这n个孩子，他们住在的家庭有且仅有一个经纬度坐标。但是在一个经纬度坐标上可能有几个孩子的家庭存在。（注意，这里所有的经纬度坐标里面的数字全部为整数）。圣诞老人的列表中第一个孩子和最后一个孩子的经纬度坐标已经确定（也就是说他必须给第一个孩子和最后一个孩子送礼物），而且现在圣诞老人就处在第一个孩子的经纬度坐标上。事实上，圣诞老人并不是可以在任意两个经纬度坐标之间所以穿梭，因为有高山、河流、风向等因素的影响。而且如果处于经纬度为A的坐标能够穿梭到经纬度为B的坐标，那么经纬度为B的坐标不一定能够穿梭到经纬度为A的坐标上。

所以，圣诞老人需要确定一个行程，即从第一个孩子到最后一个孩子给他们送礼走过的行程最短，以便再回到北极圣诞区参加极光表演。

格式

输入格式

第一行一个数n，代表有n个孩子。

接下来n行，每一行有如下格式的文字“[经度][W/E] [纬度][N/S]”。比如说某一行可能会写出：125W 56S，表示第i个孩子的家庭的经纬度坐标。

接下来若干行（m行），每行有两个正整数x、y（x可以等于y），表示圣诞老人可以第x个孩子的经纬度坐标飞向第y个孩子的经纬度坐标。

输出格式

一个实数，保留两位小数，即为最短的行程（单位是千米）。如果不可能给最后一个孩子送上礼物，则输出一行“Impossible”。

样例1

样例输入1

7
20E 90N
132E 90S
58E 45N
1W 23S
123W 13N
32E 15N
180W 02S
1 2
1 3
2 4
3 5
4 5
3 7
4 6
5 7
6 7

样例输出1

17635.54

限制

各个测试点1s，对于大数据最多为2s

提示

1<=n<=10000，1<=m<=100000，1<=x,y<=n
对于50%的数据，保证n<=1000且m<=1000。这些数据每个数据点8分，其他的数据每个数据点12分。

需要注意的是，在球体上两个点之间的距离是指这两个点在球体上经过这两个点的大圆上所截的弧长。对于经纬度方面不太清楚的，可以去搜索引擎查找相关的资料。

对于Pascal语言的提示：调用math单元（uses math）可以使用arcsin等扩展的数学函数。