104 - Arbitrage

所謂的「三角套匯 (arbitrage)」就是在幾種外幣中做金錢的交易,期待從匯差中獲取少許的利潤。例如:1 元美金可以買 0.7 英鎊,1 元英鎊可以買 9.5 法朗,1 元法朗可以買 0.16 美金。所以如果我們把 1 元美金換成英鎊,再把英鎊換成法朗,最後再把法朗換回美金,那麼最後得到的美金將是:1*0.7*9.5*0.16=1.064 美元。也就是說我們可以從中獲取匯差 0.064 美元,相當於賺了 6.4% 。

請你寫一個程式找出是否有這樣套匯的情況,可以獲取如上所述的利益。

要產生一個成功的套匯,在換外幣的過程中,開始的幣種一定得等於最後的幣種。但是從哪一種開始都可以。

Input

輸入含有多組測試資料。

每組測試資料的第一列,有一個整數 n ($2\leq{n}\leq{20}$),代表共有多少種幣種。

接下來的 n 列代表這 n 種外幣之間的匯率轉換表。每列有 n-1 個數。這 n-1 個數分別代表該幣種 1 元可以換取其他幣種多少元 (自己換自己當然是 1,所以不會出現)。所以第 1 列的 n-1 個數依序分別代表第 1 種外幣 1 元可以換取,第 2 種外幣,第 3 種外幣,第 4 種外幣 … 第 n 種外幣各多少元。而第 2 列的 n-1 個數依序分別代表第 2 種外幣 1 元可以換取,第 1 種外幣,第 3 種外幣,第 4 種外幣 … 第 n 種外幣各多少元。依此類推,第 n 列的 n-1 個數依序分別代表第 n 種外幣 1 元可以換取,第 1 種外幣,第 2 種外幣,第 3 種外幣 … 第 n-1 種外幣各多少元。

請參考 Sample Input。

Output

對每組測試資料輸出一列,代表一連串幣種轉換的動作,並且套匯獲利需大於 1% (>0.01)。如果有不止一種轉換可以獲取超過 1% 的利益,請輸出轉換次數最少的。如果轉換次數最少的不止一種,那麼任何一種都可以。請注意:在這裡只要求轉換次數最少,並沒有要求獲利要最大,只要能大於 1% 就可以了。

另外,國稅局還規定最多只能轉換 n 次 (n 是幣種的數目)。像 1, 2, 1 這樣的轉換次數為 2。

如果在 n 次的轉換內都無法獲利超過 1%,請輸出 no arbitrage sequence exists。

Sample Input

3
1.2 .89
.88 5.1
1.1 0.15
4
3.1    0.0023    0.35
0.21   0.00353   8.13 
200    180.559   10.339
2.11   0.089     0.06111
2
2.0
0.45

Sample Output

1 2 1
1 2 4 1
no arbitrage sequence exists