题目描述

A国有 $n$ 个城市，第 $i$ 个城市的名字叫 $S_i$，坐标在 $(x_i,y_i)$。

小G有 $m$ 次旅游，每次从城市 $a_i$ 飞到 $b_i$，并且他走的是直线距离，求这两个城市间的距离是多少。

输入格式

第一行两个正整数 $n,m$，表示城市数和旅游次数。

第 $2$ 到 $n+1$ 行，每行一个字符串 $s_i$ 和两个整数 $x_i,y_i$，表示第 $i$ 个城市的名字和坐标。

第 $n+2$ 到 $n+m+1$ 行，每行两个字符串 $a_i$ 和 $b_i$，表示本次旅游的起点和终点。

输出格式

共 $m$ 行，第 $i$ 行一个实数表示第 $i$ 次旅游所经过的两座城市之间的距离，答案保留 $6$ 位小数。

4 3
BeiJing 4 4
ShangHai 2 4
GuangZhou -3 0
ShenZhen 2 0
BeiJing ShangHai
GuangZhou ShenZhen
GuangZhou ShangHai

2.000000
5.000000
6.403124

数据范围

对于 $60\%$ 的数据，$2≤n≤1000$

对于 $100\%$ 的数据，$2≤n,m≤10^5$，每个城市名字长度在 $10$ 个字符以内，保证仅由大小写英文字母组成，保证 $n$ 个城市名字、坐标互不相同，保证每次旅行的起点和终点存在，$∣a∣,∣b∣≤10^9$。