Vũ Điệu Cầu Thang Hogwarts

Bên trong lâu đài Hogwarts có một khu vực đặc biệt gồm $N$ hàng và $M$ cột các phòng học, được bố trí theo dạng lưới. Một số phòng đã bị niêm phong bởi phép thuật và Harry không thể đi vào.

Hệ thống cầu thang ma thuật của Hogwarts hoạt động theo $K$ giai đoạn. Trong mỗi giai đoạn, toàn bộ cầu thang sẽ dịch chuyển theo một hướng cố định (lên, xuống, trái, hoặc phải). Tại mỗi đơn vị thời gian trong một giai đoạn, Harry có thể chọn:

• Di chuyển một bước theo hướng cầu thang đang dịch chuyển (nếu ô đích không bị niêm phong và nằm trong lưới), hoặc
• Đứng yên tại chỗ.

Harry bắt đầu tại phòng $(x,y)$ trước khi giai đoạn đầu tiên bắt đầu. Hãy tìm số bước di chuyển lớn nhất mà Harry có thể thực hiện được.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $N$, $M$, $K$ — kích thước lưới và số giai đoạn.
• $N$ dòng tiếp theo, mỗi dòng chứa $M$ ký tự: '.' là phòng trống, 'x' là phòng bị niêm phong.
• Dòng tiếp theo chứa hai số nguyên $x$, $y$ — vị trí bắt đầu của Harry ($1$-indexed). Đảm bảo ô $(x,y)$ là phòng trống.
• $K$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $s_i$, $t_i$, $d_i$ — giai đoạn thứ $i$ kéo dài từ thời điểm $s_i$ đến $t_i$ (bao gồm cả hai đầu), hướng di chuyển $d_i$:
  • $1$ = lên (hàng giảm)
  • $2$ = xuống (hàng tăng)
  • $3$ = trái (cột giảm)
  • $4$ = phải (cột tăng)

Các giai đoạn nối tiếp nhau liên tục: $s_1=1$ và $s_{i+1}=t_i+1$.

Dữ liệu ra

In ra một số nguyên duy nhất — số bước di chuyển lớn nhất mà Harry có thể thực hiện.

Ràng buộc

• $1\le N,M\le 200$
• $1\le K\le 200$
• $1\le x\le N$, $1\le y\le M$
• Tổng thời gian $T=t_K\le 40000$
• Ô $(x,y)$ luôn là '.'

Ví dụ

Ghi chú

Harry chỉ có thể di chuyển theo hướng mà cầu thang đang hoạt động trong giai đoạn hiện tại. Ở mỗi đơn vị thời gian, Harry hoặc đi một bước theo hướng đó, hoặc đứng yên. Harry không thể di chuyển ngược hướng hoặc sang hướng khác.