168 - Theseus and the Minotaur

在希臘神話中，有一個傳說「忒修斯(Theseus)和牛頭怪」 這是一個不太可能的故事，故事中參雜了一個牛頭的怪物、充滿曲折的地下迷宮、失戀的女孩以及線球。在這次競賽的教育性質上，我們要揭露這個真實故事。

迷宮有很多洞窟，每個洞窟經由幾個通道可以通往其他洞窟，而其中幾個只能單向通行。為了設下陷阱抓到牛頭怪，忒修斯發現牛頭怪怕光，於是帶著大量的蠟燭進入迷宮。

忒修斯在迷宮四處找尋，最後他聽到牛頭怪從通道另一端傳來的聲音，從那個時刻開始，忒修斯點燃蠟燭並且展開追逐行動，牛頭怪會離開原本的洞窟，並且移動到下一個洞窟。而忒修斯慢慢地跟著牛頭怪移動，當每經過 k 個洞窟，他將會在此點燃一個蠟燭放下，當他快速點燃蠟燭後，會繼續跟蹤牛頭怪。由於有蠟燭的洞窟牛頭怪不會靠近，因此將會限制住牛頭怪的移動。

當牛頭怪離開洞窟時，會依序檢察其它不存在蠟燭的洞窟，找到第一個可去的地方並且移動，最後牛頭怪會被困住無法移動，忒修斯將可以戰勝牠。

迷宮類似於下圖表示，而牛頭怪離開的時候就好比按照字典順序檢查：

假設忒修斯在 C，他會聽到牛頭怪從 A 傳來的聲音，假設 k = 3，而走的順序依序為 A, B, D(忒修斯在此放下點燃的蠟燭), G, E, F(再放一個), H, E, G(再放一個), H, E(牛頭怪最後受困的地點)。

備註翻譯：由於忒修斯尾隨牠，牛頭怪不會走回上次的洞窟。



寫一個程式模擬整個追逐過程，所有洞窟將只會用大寫英文字母表示，並且按照順序打印出蠟燭的放置，以及最後牛頭怪被困的洞窟。

Input

輸入有多組測資，每組用一行表示圖形以及忒修斯位置、牛頭怪位置、k。

每一行不超過 255 個字元。

讀到 '#' 結束程式。

Output

對於每組測資，按照順序輸出蠟燭的放置(追逐時的順序)，以及牛頭怪最後的位置。

Sample input

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
#

Sample output

D F G /E