SP3133 GORELIAN - Here We Go(relians) Again

戈雷利安人是一个好战的种族，喜欢把征服新的世界当作娱乐活动。由于他们天性暴力又热爱刺激，保护领导人安全成为了一项紧迫任务。戈雷利安的安全计划之一是每天更换城市的交通模式，为了让政府官员能够以最快速度抵达政府大楼。 幸运的是，对于担任戈雷利安交通部长的你来说，所有的戈雷利安城市都是按照矩形网格布局的。每个街区是一个边长为 2520 蕾尔的正方形（蕾尔是戈雷利安的官方长度单位）。两个相邻交叉口之间的限速是固定的，范围可以是 1 到 9 蕾尔/哔（哔是戈雷利安的官方时间单位）。由于戈雷利安人禁止使用小数，所以限速始终是整数。这解释了为什么每个街区的长度为 2520 蕾尔：因为 2520 是 1 到 9 的最小公倍��。这使得从一个交叉口移动到相邻交叉口的时间始终是整数个哔。 在所有的戈雷利安城市中，政府住宅位于城市的西北角，而政府大楼则在东南角。街道可能是单向、双向，或因维修而关闭（由于频繁更改交通模式，事故会频繁发生）。你的任务是根据规定的街道限速、方向和封闭信息，找出从政府住宅到政府大楼的最快路径。（注意，由于交通方向和道路封闭的情况，可能不存在任何可行路线，在这种情况下，政府会宣布戈雷利安官员临时休假一天。）

输入包含多组城市，每组城市都需要找出最快路径。每组数据的第一行有两个整数，表示城市的垂直和水平街区数量。最小的城市为单个街区，即 1×1，最大的城市为 20×20 个街区。接下来是各条街道的速度限制和方向信息，一次输入一行。首先输入最北面的东西向区段的数据，然后是最北面南北向区段的数据。接着是下一行的东西向街道，随后是南北街道，依此类推，直到最南面的东西向街道。速度限制和方向依次从西至东给出，每个都包括一个 0 到 9 的整数表示速度限制和一个符号表示允许的行驶方向。速度为 0 表示道路关闭。所有数字和符号用空格分隔。对于东西向街道，符号 '*' 表示双向通行，'' 表示只允许从西向东。对于南北向街道，'*' 同样表示双向通行，'v' 表示只允许从北向南，'^' 表示只允许从南向北。速度为零的道路总是加上一个 '*'。输入数据在两个维度大小皆为零时结束。

对于每组输入情景，输出一行包含最短路径所需的哔数，后跟一个空格和 "blips"。如果没有路径可行，则输出一行，内容仅为 "Holiday"。 **本翻译由 AI 自动生成**