题目描述

有一个 $N \times N$ 的网格，其中第 $i$ 行（从上往下）第 $j$ 列（从左往右）的单元格包含整数 $N \times (i-1) + j$。

在 $T$ 个回合中，将会声明不同的整数。在第 $i$ 个回合，整数 $A_i$ 被声明，包含 $A_i$ 的单元格被标记。确定第一次达成 Bingo 的回合数。如果在 $T$ 个回合内没有达成 Bingo，请输出 -1。

这里，达成 Bingo 意味着满足以下条件之一：

• 存在一行中所有 $N$ 个单元格都被标记。
• 存在一列中所有 $N$ 个单元格都被标记。
• 存在一条对角线（从左上到右下或从右上到左下）中所有 $N$ 个单元格都被标记。

输入格式

输入从标准输入中以下列格式给出：

$N$ $T$

$A_1$ $A_2$ $\ldots$ $A_T$

输出格式

如果在 $T$ 个回合内达成 Bingo，输出第一次达成 Bingo 的回合数；否则，输出 -1。

样例

3 5
5 1 8 9 7

4

3 5
4 2 9 7 5

-1

4 12
13 9 6 5 2 7 16 14 8 3 10 11

9

样例解释

【样例1说明】
网格状态变化如下。在第 $4$ 个回合首次达成 Bingo。

【样例2说明】
在五个回合内没有达成 Bingo，所以输出 -1。

数据范围

• $2 \leq N \leq 2 \times 10^3$
• $1 \leq T \leq \min(N^2, 2 \times 10^5)$
• $1 \leq A_i \leq N^2$。
• 如果 $i \neq j$ 则 $A_i \neq A_j$ 。所有输入值都是整数。

来源

• AtCoder ABC355C