33951번 - 사각형 모험

문제

포닉스는 $N\times M$ 크기의 격자에서 살고 있었다. 각 칸은 정사각형 모양이며, 격자의 각 칸에서는 상하좌우로 인접한 칸으로 자유롭게 이동할 수 있다. $r$번째 행, $c$번째 열에 위치한 칸을 $(r,c)$라 하자.

포닉스가 살고 있는 격자는 큰 도시로 발전하였다. $(1,1)$에는 포닉스의 집이, $(N,M)$에는 시장이 위치해 있다. 포닉스의 집과 시장을 포함한 격자의 모든 칸에는 사과 농장과 바나나 농장 중 하나가 위치하고 있다. 사과 농장이 있는 칸에 방문하면 사과를 1ドル$개, 바나나 농장이 있는 칸에 방문하면 바나나를 1ドル$개 얻는다. 포닉스는 욕심쟁이이기 때문에 과일을 얻지 않는 경우는 없다.

포닉스는 집에서 출발한 후 가능한 짧은 경로로 시장에 도착해 쌀국수를 사 먹으려 한다. 허나 문제는 사과와 바나나, 쌀국수의 가격이 계속 변한다는 것이다. 따라서 포닉스는 앞으로 $K$번에 걸쳐 시장 가격을 예측하려 한다.

$i$번째 예측에서 사과 하나, 바나나 하나, 쌀국수의 예상 가격은 각각 $A_i,ドル $B_i,ドル $C_i$이다. 포닉스가 시장에 도착했을 때 포닉스가 가진 사과와 바나나를 모두 팔아 얻은 돈이 $C_i$와 정확히 같다면, 포닉스는 쌀국수를 사 먹을 수 있다.

각 예측에 대해 포닉스가 적절한 경로로 시장에 도착해 쌀국수를 사 먹을 수 있는지 판별하여라.

입력

첫 번째 줄에 격자의 크기를 나타내는 두 정수 $N,ドル $M$과 예측의 수 $K$가 공백으로 구분되어 주어진다. $(2\le N,M\le 2,円 000;1\le K\le 500 000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 길이 $M$의 문자열이 주어진다. $i$번째 줄의 $j$번째 문자는 $(i,j)$에 위치한 과일 농장의 종류를 의미한다. A는 사과 농장을, B는 바나나 농장을 의미한다.

$N+2$번째 줄부터 $K$개의 줄에 걸쳐, $N+1+i$번째 줄에 각각 $i$번째 예측의 사과 하나, 바나나 하나, 쌀국수의 가격을 의미하는 세 정수 $A_i,ドル $B_i,ドル $C_i$가 공백으로 구분되어 주어진다. $(1\le A_i,B_i\le 500,円 000;1\le C_i\le 2\times 10^9)$

출력

$K$개의 줄에 걸쳐 $i$번째 예측에 대해 포닉스가 쌀국수를 사 먹을 수 있다면 YES, 그렇지 않으면 NO를 한 줄에 하나씩 순서대로 출력한다.

제한

힌트