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

题目描述：

荷兰铁路公司NS近来运营不佳。由于技术问题，他们被迫临时取消大量列车班次，这给乘坐火车上下学的学生带来了极大困扰。

最令人头疼的是取消的随机性。在官方发车时间前，没人知道列车是否会取消。由于通常存在多条从家到学校的路线，人们常会感叹"早知道就选另一条路线了"。

最近NS统计部门发现了一个革命性解决方案。他们注意到某些列车班次更容易被取消。为了帮助乘客，他们决定公布这些信息。新版时刻表不仅会显示每班列车的发车和到达时间，还会标注其取消概率。

NS的行程规划软件原先只寻找最快路线，现在需要升级为寻找最可能准时到达的路线。这样乘客可以避开易出问题的列车，选择稍慢但更可靠的路线。

给定新版时刻表、出发站和时间、目的站和期望到达时间，找出最可能准时到达目的地的路线。

输入格式：

• 首行为测试用例数
• 每个测试用例包含：
  • 列车数量n（n≤100）
  • n行列车信息：出发站x 发车时间tx 目的站y（x≠y） 到达时间ty（tx<ty） 取消概率p
    • 车站用大写字母A-L表示
    • 时间格式hh:mm（00≤hh<24，00≤mm<60）
    • 取消概率p为实数（0.0≤p<1.0）
  • 一行查询：出发站a 最早出发时间ta 目的站b（a≠b） 期望到达时间tb（ta<tb）

输出格式： 每个测试用例输出两行：

1. 最佳路线（车站序列，空格分隔）
2. 准时到达概率（保留4位小数，四舍五入）

示例输入输出：

输入示例1：

2
3
A 12:00 B 12:15 0.1
A 12:10 B 12:14 0.23
A 12:20 B 12:30 0.456
A 12:00 B 12:30
4
A 12:00 B 12:15 0.1
A 12:05 B 12:13 0.15
B 12:20 C 12:35 0.12
A 12:15 C 12:33 0.4
A 12:00 C 13:00

输出示例1：

A B
0.9895
A B C
0.8668