Description

On the contrary, social circles come in all kinds of shapes, and the common divisors are pitifully small. It seems hard to keep one’s own personality, and thus one becomes a boring person.

Now abstract interpersonal relationships into an $n \times m$ rectangle. Each person’s initial personality is $a_{i,j}$. Starting from the second day, each person will build relationships with the four people up, down, left, and right (if they exist), and their personality becomes the greatest common divisor of their own personality yesterday and the personalities of the surrounding people. Then, for the person at row $x$ and column $y$, after how many days will their personality become $1$?

---

Simplified statement

There is an $n \times m$ matrix $a$. Define one transformation on a matrix as: change every element in the matrix into the greatest common divisor of itself and its four adjacent elements (up, down, left, right; ignore non-existing ones). Ask for the minimum number of transformations needed for $a_{x,y}$ to become $1$. If $a_{x,y}$ can become $1$ after some number of transformations, output the minimum number; otherwise output $-1$.

Input Format

The first line contains two integers $n, m$, indicating the number of rows and columns of the matrix.

The next $n$ lines each contain $m$ integers. The integer $a_{i,j}$ in row $i$ and column $j$ describes the initial personality of the person at that position.

The next line contains two integers $x, y$, indicating the position of a specified person.

Output Format

Output one integer $d$, meaning that the personality of the person at row $x$ and column $y$ will become $1$ after $d$ days. In particular, if it will never become $1$, output $-1$.

2 2
2 2
1 2
2 1

0

2 2
2 2 
2 2
1 1

-1

3 3
3 2 3
2 3 2
3 2 3
2 2

1

Hint

Sample explanation 3

The personality matrix on the first day (i.e. the initial matrix) is

$$\begin{pmatrix} 3&2&3\\ 2&3&2\\ 3&2&3 \end{pmatrix}$$

The personality matrix on the second day is

$$\begin{pmatrix} 1&1&1\\ 1&1&1\\ 1&1&1 \end{pmatrix}$$

It can be seen that after only one day, $a_{2,2}$ becomes $1$, so the answer is $1$.

Constraints and conventions

This problem uses bundled tests.

For $100\%$ of the testdata, $1\le n,m\le 2\times 10^3$, $1\le a_{i,j}\le 10^{18}$, $1\le x\le n$, $1\le y\le m$.

Subtask	Score	$n,m$	Special constraints
1	1	/	Guarantee that the personality at the given position will never become $1$
2			Guarantee that $a_{x,y}=1$
3		$\le 2$	/
4	10	$\le 10^2$
5	30	$\le 5\times 10^2$
6	10	/	Guarantee that for all $a_{i,j} \le 2$
7			Guarantee that both $x$ and $y$ equal $1$
8	35		/

Translated by ChatGPT 5