I - Bingo Game
問題文
寺子さんはビンゴゲームに参加しています。寺子さんが持っているビンゴカードは$N$行$N$列のマス目からなり、上から $i$ 行目、左から $j$ 列目のマスには相異なる整数 $A_{i,j}$ が書かれています。
長さ$M$の数列$B = (B_1, B_2,\dots, B_M)$が前から順番に呼び上げられます。呼び上げられた数字がビンゴカードに存在する場合、そのマスは「開けられた」と見なされます。
ビンゴカードにおいて、任意の行または列または対角線のすべてのマスが「開けられた」場合、ビンゴが成立します。
ビンゴが初めて成立するのは、呼び上げられた数字のうち、何個目が呼び上げられたときかを求めてください。ビンゴが成立しない場合は-1を出力してください。
制約
- $2 \le N \le 10^3$
- $1 \le A_{i, j} \le 10^6$
- $1 \le M \le 10^4$
- ビンゴカードに書かれている整数$A_{i,j}$は$1$以上$10^6$以下の相異なる整数
- 呼び上げられる整数$B_k$は$1$以上$10^6$以下の相異なる整数
入力
$N \quad M$
$A_{1,1} \quad A_{1,2} \quad \dots \quad A_{1,j} \quad \dots \quad A_{1,N}$
$A_{2,1} \quad A_{2,2} \quad \dots \quad A_{2,j} \quad \dots \quad A_{2,N}$
$\vdots \quad \quad \vdots \quad \quad \ddots \quad \vdots \quad \quad \ddots \quad \vdots$
$A_{i,1} \quad A_{i,2} \quad \dots \quad A_{i,j} \quad \dots \quad A_{i,N}$
$\vdots \quad \quad \vdots \quad \quad \ddots \quad \vdots \quad \quad \ddots \quad \vdots$
$A_{N,1} \quad A_{N,2} \quad \dots \quad A_{N,j} \quad \dots \quad A_{N,N}$
$B_1 \quad B_2 \quad \dots \quad B_M$
出力
1行出力せよ
ビンゴが成立するとき、呼び上げられた数字のうち、何個目が呼び上げられたときかを出力せよ。ビンゴが成立しない場合は-1を出力せよ。
3 7
1 2 3
4 5 6
7 8 9
5 2 8 1 4 6 3
3
3個目の数字が呼び上げられた時点で、2列目のすべてのマスが「開けられた」ため、ビンゴが成立します。
2 3
10 20
30 40
50 60 70
-1
呼び上げられた数字のいずれもビンゴカードに存在しないため、ビンゴは成立しません。
3 7
1 2 3
7 9 8
4 5 6
5 2 8 1 4 6 3
6
6個目の数字が呼び上げられた時点で、3行目のすべてのマスが「開けられた」ため、ビンゴが成立します。
3 5
1 2 3
4 5 6
7 8 9
1 2 4 5 9
5
5個目の数字が呼び上げられた時点で、左上から右下への対角線のすべてのマスが「開けられた」ため、ビンゴが成立します。