許多壓縮法則並不會直接壓縮輸入的訊息，他們通常在執行壓縮前會對輸入的訊息做一些前置處理，能讓此訊息有效率地壓縮。以下說明一種前置處理的方式，稱之為Burrows-Wheeler (BW)轉換。

假設輸入一個字串S，其包含的字母個數為N，則BW 轉換的第一個步驟便是依據下列的兩個式子另外產生N個新字串，分別為S₁, S₂,...,S_N。

1. 字串S₁等於S。


2. 字串S_k向左位移一個字母，第一個字母放到最後一個位置，即可得字串S_k+1，其中1<=k<N。

以下為BW 轉換的第一個步驟之實例，假設輸入一個字串S="WHEELER"，其中字母個數N = 7，則產生的新字串如下所示：

在BW 轉換之第二個步驟中我們將這N個新字串排序。首先依據每個字串之第一個字母(從最左邊算起)排序，字母在排序時的大小順序為A > B > C > … > Z。若有某些字串第一個字母相同，則這些字串間的排序依照第二個字母。若仍相同，則依照第三個字母，依此類推到第N個字母為止。承續第一步驟的實例，其排序結果如下所示：

其中S₃,S₄,S₆字串中的第一個字母皆相同，因此這三個字串的排序順序由第二個字母比較而得。
在BW 轉換完成後，我們需要的結果為兩個：

1. 排序後第N欄形成的字串；即為依序抓出每列的最後一個字母形成需要的字串，所以在本例中最後一欄形成的字串為"HELWEER"；


2. S₂所在的列位置；在本例中為4 (列數從1 開始計算，非從0 開始)。

本題即是請你撰寫上述Burrows-Wheeler 轉換的程式。

Constraints

輸入字串及產生的新字串中僅限於大寫的英文字母，輸入的字串中至少有兩個相異字母。