Cheng 因為在動漫界養了太多老婆，犯下了滔天大罪被 pudding 抓去關，想逃跑的 Cheng 在這個監獄裡面探索著......。
Cheng 發現這個監獄有著神秘魔法，監獄原本是 $N \times M$ 的矩形，若走超過邊界則會被傳送到另一邊，換言之：

• 定義座標 $(x,\ y)$ 代表由上到下第 $x$ 個橫排、由左到右第 $y$ 個直排的位置。
• 若在 $(1,\ y)$，如果往上走，因為會碰到上方的邊界，傳送到 $(N,\ y)$。
• 若在 $(N,\ y)$，如果往下走，因為會碰到下方的邊界，傳送到 $(1,\ y)$。
• 若在 $(x,\ 1)$，如果往左走，因為會碰到左方的邊界，傳送到 $(x,\ M)$。
• 若在 $(x,\ M)$，如果往右走，因為會碰到右方的邊界，傳送到 $(x,\ 1)$。

這就是這個監獄的神秘魔法力量，但似乎因為魔法力量太過強大，強大到魔法力量會溢散出來，Cheng 是個觀察力十分好的同學，他發現這個監獄中 $(x,\ y)$ 座標每秒會溢散出 $a_{x,\ y}$ 單位的魔法力量。Cheng 可以蒐集這些魔法力量，如果蒐集達到 $K$ 單位的魔法力量就可以靠著這些魔法力量破壞監獄逃出來！

Cheng 告訴你第 $0$ 秒的時候他在 $(s,\ t)$ 這個座標 (他一開始也會蒐集到這個座標上的魔法力量)，他接下來會告訴你他每秒會怎麼走，這會是一個字串 $S$，每個字元代表他每秒的操作，如下：

• U 代表向上走。
• D 代表向下走。
• R 代表向右走。
• L 代表向左走。

請你告訴 Cheng 在第幾秒才會蒐集到足夠的魔法力量讓他逃離這個監獄？如果在他講的操作執行完過後都無法蒐集到足夠的魔法力量則輸出 $-1$。

對於所有測試資料：
$1 \le N,\ M \le 10$
$0 \le K \le 10$^$9$
$1 \le s \le N$
$1 \le t \le M$
$0 \le a_{i,\ j} \le 100$
$1 \le |S| \le 10$^$6$ ，$|S|$ 代表字串 $S$ 的長度。
$S_i \in$ {U, D, L, R}，$S_i$ 代表字串 $S$ 中的第 $i$ 個字元。