Luka lại cảm thấy nhàm chán trong lớp hóa học. Lần này, anh ấy đang chơi với vi khuẩn thông minh. Anh ta đã sắp xếp vi khuẩn ~K~ của mình trên một bảng hình chữ nhật chia thành ~N~ hàng, được đánh số từ ~1~ đến ~N~ bắt đầu từ trên cùng và cột ~M~, được dán nhãn đánh số từ ~1~ đến ~M~ bắt đầu từ bên trái.

Mỗi vi khuẩn bắt đầu cuộc phiêu lưu của mình trong một tế bào nhất định, đối mặt với một trong bốn tế bào lân cận và thực hiện các hành động sau mỗi giây:

1. Đọc số ~X~ dành riêng cho vi khuẩn đó trong ô hiện tại.
2. Xoay 90 độ theo chiều kim đồng hồ, ~X~ lần.
3. Nếu nó hướng về một ô bên ngoài bảng, nó sẽ quay 180 độ.
4. Cuối cùng, nó di chuyển đến ô mà nó đang đối mặt.

Luka đã đặt một cái bẫy trong một phòng giam. Cái bẫy sẽ kích hoạt và tiêu diệt vi khuẩn ngay khi chúng bước lên tế bào đó trong cùng một giây.

Vì hôm nay Luka chỉ có hai giờ học hóa học nên hãy giúp cậu ấy xác định xem trò chơi sẽ kéo dài bao lâu, tính bằng giây.

Input

• Dòng đầu tiên của dữ liệu đầu vào chứa các số nguyên dương ~N~ ~(3 ≤ N \le 50)~, ~M~ ~(3 \le M \le 50)~ và ~K~ ~(1 \le K \le 5)~.
• Dòng đầu vào thứ hai chứa các số nguyên dương ~X~ và ~Y~, hàng và cột nơi Luka đã đặt bẫy.
• Phần còn lại của dữ liệu đầu vào bao gồm các mô tả về vi khuẩn, cho mỗi vi khuẩn ~i~ từ ~1~ đến ~K~: - hai số nguyên dương ~X_i~, ~Y_i~ – hàng và cột của ô bắt đầu của vi khuẩn ~i~ và ký tự ~C_i~ biểu thị hướng xuất phát của vi khuẩn. hướng về phía (~U~ – lên, ~R~ – phải, ~D~ – xuống, ~L~ – trái). – Ma trận ~N \times M~ gồm các chữ số từ 0 đến 9; chữ số ở hàng ~x~ và cột ~y~ đại diện cho số trong ô ~(x, y)~ dành riêng cho vi khuẩn i.

Output

• Dòng đầu ra đầu tiên và duy nhất phải chứa tổng thời lượng trò chơi của Luka, tính bằng giây. Nếu trò chơi không bao giờ kết thúc, ghi ~-1~.

Sample Input 1

3 3 1
2 2
1 1 R
010
000
000

Sample Output 1

3

Sample Input 2

3 4 2
2 2
3 4 R
2327
6009
2112
3 2 R
1310
2101
1301

Sample Output 2

8

Sample Input 3

4 4 3
4 3
1 1 U
1001
0240
3322
2327
1 3 L
9521
2390
3020
2421
2 2 D
3397
2013
1102
7302

Sample Output 3

296