택배 배달

택배 기사가 창고 A에서 출발하여 창고 B까지 최단 시간으로 이동하려고 한다.

도로망은 R행 C열의 격자로 표현된다. 각 칸은 다음 중 하나이다:

• #: 도로 (이동 가능)
• .: 잔디 (이동 불가)
• A: 출발 창고
• B: 도착 창고
• 숫자 0~9: 교차로 (신호등 있음)

교차로에서는 신호등에 따라 이동이 제한된다. 신호등 i의 정보은 EW_i NS_i로 주어지며:

• 매 주기의 처음 EW_i초간은 동서(좌우) 방향 이동만 허용
• 이후 NS_i초간은 남북(상하) 방향 이동만 허용

시간 0에서 시작하여 교차로 칸에 진입할 때 신호등 규칙을 따른다. 인접한 칸으로 이동하는 데 1초가 걸린다.

입력

첫째 줄에 격자의 크기 R과 C가 주어진다. (1 <= R, C <= 20)

둘째 줄부터 R개의 줄에 걸쳐 격자 정보가 주어진다.

그 다음 줄에 교차로의 개수 L이 주어진다. (0 <= L <= 10)

이후 L개의 줄에 걸쳐 교차로 번호와 EW_i NS_i가 주어진다. (1 <= EW_i, NS_i <= 10)

출력

A에서 B까지의 최단 시간을 출력한다. 이동할 수 없는 경우 -1을 출력한다.

입출력 예시

입력 1

1 5
A#0#B
1
0 2 1

출력 1

4

입력 2

1 3
A0B
1
0 3 2

출력 2

2