Peykan Cũ trên phố cổ

Thành phố Cổ được biểu diễn bằng một lưới hình chữ nhật kích thước $m\times n$ ô. Mỗi ô là một trong ba loại:

• Toà nhà, ký hiệu bằng #. Không đi qua được.
• Ô đường, ký hiệu bằng một chữ số từ 1 đến 9. Chữ số này là thời gian (theo phút) cần để đi từ ô này sang một ô kề cạnh bất kỳ.
• Ngã tư, ký hiệu bằng một chữ cái thường từ a đến z (mỗi ngã tư có một tên riêng, không trùng). Từ một ngã tư đi sang một ô đường kề cạnh mất đúng $1$ phút.

Hai ô được gọi là kề cạnh nếu chúng chia sẻ một cạnh chung. Tất cả đường đều có chiều rộng đúng $1$ ô và chỉ chạy theo phương ngang hoặc phương dọc. Ở hai đầu mỗi đường luôn có một ngã tư. Không có hai ô của hai con đường khác nhau kề cạnh nhau, và không có hai ngã tư kề cạnh nhau.

Trong một dịp lễ, chiếc xe Peykan Cũ đi theo một hành trình đặc biệt. Hành trình bắt đầu tại một ô đường, đi qua một dãy ngã tư theo thứ tự cho trước, và kết thúc tại một ô đường. Sau khi chạm ô kết thúc, Peykan dừng lại ở đó mãi mãi. Peykan luôn đi theo hành trình ngắn nhất đi qua đúng dãy ngã tư đã cho theo thứ tự. Peykan có thể đi qua cùng một ô nhiều lần.

Cho vị trí xuất phát, dãy ngã tư và vị trí kết thúc, hãy xác định vị trí của Peykan đúng $k$ phút sau khi bắt đầu di chuyển.

Toạ độ ô: ô ở hàng $i$, cột $j$ có toạ độ $(i,j)$, với $1\le i\le m$ và $1\le j\le n$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $m$, $n$ và $k$.
• $m$ dòng tiếp theo mô tả bản đồ, mỗi dòng gồm $n$ ký tự như đã mô tả ở trên.
• Dòng cuối chứa: hai số nguyên $r_s$ và $c_s$ (toạ độ ô xuất phát), một chuỗi $s$ (dãy tên các ngã tư cần đi qua theo thứ tự), rồi hai số nguyên $r_e$ và $c_e$ (toạ độ ô kết thúc).

Chuỗi $s$ có độ dài từ $1$ đến $1000$ và không chứa hai ký tự liên tiếp giống nhau. Ô xuất phát và ô kết thúc đều là ô đường. Đảm bảo tồn tại một hành trình hợp lệ đi từ ô xuất phát, qua đúng dãy ngã tư $s$ theo thứ tự, tới ô kết thúc.

Dữ liệu ra

In ra một dòng chứa hai số nguyên $r_f$ và $c_f$ — toạ độ của Peykan sau đúng $k$ phút.

Ràng buộc

• $3\le m,n\le 100$
• $1\le k\le {10}^5$
• $1\le r_s,r_e\le m$
• $1\le c_s,c_e\le n$
• $1\le |s|\le 1000$

Ví dụ