Contest Duration: - (local time) (300 minutes) Back to Home
F - Coloring map /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

この地図の州 i を色 C_i で塗るとき、以下の条件は満たされていますか？

制約

• 1 \leq H \leq 200
• 1 \leq W \leq 200
• 1\leq N \leq \min(100,H\times W)
• 1\leq A_{i,j} \leq N
• 全ての k(1\leq k\leq N) について、A_{i,j}=k を満たす (i,j) が少なくとも 1 つ存在する
• 1\leq C_i \leq N
• 入力に含まれる値は全て整数である

入力

H W N
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
C_1 C_2 \ldots C_N


入力例 1

2 4 3
1 1 2 3
1 2 2 3
2 3 3


出力例 1

No


2 と州 3 は隣り合っていますが同じ色で塗られているので、条件を満たしません。

入力例 2

3 5 4
1 1 1 3 2
1 2 1 3 4
1 1 1 3 2
3 1 4 3


出力例 2

Yes


1 のように穴が空いている場合もあります。
また、州 2 のように非連結である場合もあります。

入力例 3

2 2 3
1 2
3 1
1 2 2


出力例 3

Yes


2 と州 3 は上下左右に隣り合っていないので、同じ色で塗られていても条件を満たします。

Score : 7 points

Problem Statement

The Kingdom of Takahashi consists of N states numbered 1 to N.
The map of the kingdom is a grid with H rows and W columns. The square at the i-th row from the top and j-th column from the left belongs to State A_{i,j}.

Is the condition below satisfied when painting State i in Color C_i in this map?

Different states that are vertically or horizontally adjacent are painted in different colors.

Constraints

• 1 \leq H \leq 200
• 1 \leq W \leq 200
• 1\leq N \leq \min(100,H\times W)
• 1\leq A_{i,j} \leq N
• For every k(1\leq k\leq N), there is at least one pair (i,j) such that A_{i,j}=k.
• 1\leq C_i \leq N
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W N
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
C_1 C_2 \ldots C_N


Output

If the condition is satisfied, print Yes; otherwise, print No.

Sample Input 1

2 4 3
1 1 2 3
1 2 2 3
2 3 3


Sample Output 1

No


State 2 and State 3 are adjacent but painted in the same color, so the condition is not satisfied. (In the figure below, "色" means color.)

Sample Input 2

3 5 4
1 1 1 3 2
1 2 1 3 4
1 1 1 3 2
3 1 4 3


Sample Output 2

Yes


Some states, such as State 1 here, may have holes. Also, some states, such as State 2 here, may be disconnected.

Sample Input 3

2 2 3
1 2
3 1
1 2 2


Sample Output 3

Yes


Since State 2 and State 3 are not vertically or horizontally adjacent, painting them in the same color does not violate the condition.