本题没有可用的提交语言。

描述

您已经决定是时候启动下一个互联网地图了。你这次冒险的灵感来自于你有方向感障碍的配偶，他不关心当前在线地图系统生成的最短或最快的路线——相反，越简单越好。

操作的核心当然是计算方向的算法。你的算法必须从你庞大的全国数据库中接受地图，并产生满足客户查询的最佳路线。查询由起点、目的地和优化目标组成，优化目标可以是最短路线、最快路线或转弯最少的路线。可以保证，对于所请求的任何查询，源和目标之间都有一条路径。

Input

输入文件中有三个部分，第一部分列出城市，第二部分列出道路，第三部分列出查询。

输入的第一行是城市数量c，后面是c行，每一行包含一个城市的名称。城市名称中没有空格。

下一行是道路的数量r，后面是描述道路的r行。每条道路描述都有如下形式：

< RoadName > < CityA > < ABDistance > < ABTime > < CityB > [< BCDist > < BCTime > < CityC > [...]]

道路名称中不能有空格。道路可以穿过许多城市。城市按照道路经过的顺序出现。没有一条道路会多次穿过同一座城市。道路是双向的。沿着每对城市之间的道路行驶所需的距离和时间（都是实数）就是这两个城市之间所列的距离和时间。当沿着一条道路在多个城市之间行驶时（例如，从a到C），沿着这条道路的所有步骤的距离和时间都是累积的。

文件中其余的行分别列出一个查询。查询的形式是：

< querytype > < origin > < destination >

查询类型为时间、距离或转弯，起点和终点为城市名称。

查询以end- file结束。

输出

对于每个查询，您的输出将以一行开始：

from < origin >

以下每一行的格式为：

< roadName > to < cityname > ，其中列出了从前一个城市转向的道路，以及该道路要到达的城市。如果沿着一条道路在多个城市之间行驶，则只会列出该道路在转入另一条道路之前到达的最后一个城市。最后列出的城市将是目的地城市。

5
Chicago
DesMoines
OklahomaCity
Dallas
LosAngeles
4
I80 Chicago 300 4 DesMoines
I35 DesMoines 550 7.3 OklahomaCity 205 3 Dallas
I40 OklahomaCity 1330 20.5 LosAngeles
Rt66 Chicago 2448 46 LosAngeles
time Chicago LosAngeles
turns Chicago LosAngeles

from Chicago
I80 to DesMoines
I35 to OklahomaCity
I40 to LosAngeles
from Chicago
Rt66 to LosAngeles