Grid GCD Propagation

We are given an n × m matrix \(a\) where each element \(a_{i,j}\) represents the personality of a person at row \(i\) and column \(j\). From the second day onward, every person updates their personality by taking the greatest common divisor (GCD) of their own personality and that of their up to four neighbors (up, down, left, right). Formally, if on a given day the matrix is \(a\), then the next day the value at cell \((i,j)\) becomes

[ a_{i,j}^{(new)} = \gcd\Bigl( a_{i,j},, a_{i-1,j},, a_{i+1,j},, a_{i,j-1},, a_{i,j+1} \Bigr) ]

For a query given by \(x\) and \(y\), determine the minimum number of days needed such that the personality at cell \((x,y)\) becomes 1. If it is impossible to ever achieve a personality of 1 at that cell, output \(-1\).

Simplified Problem Statement

You are given an \(n \times m\) matrix \(a\). A transformation is defined as replacing every element with the GCD of itself and its neighbors (up, down, left, right; ignore neighbors that do not exist). For the element at cell \(a_{x,y}\), determine the minimum number of transformations required for it to become \(1\). If it is possible, output the minimum number of transformations; otherwise, output \(-1\).

Note: It can be shown that after \(d\) transformations, the value at cell \((x,y)\) becomes the GCD of all \(a_{i,j}\) such that \(|i - x| + |j - y| \le d\) (with indices considered appropriately). Thus, you need to find the smallest \(d \ge 0\) such that

[ \gcd{a_{i,j} : |i-x|+|j-y| \le d} = 1. ]

inputFormat

The first line contains four integers \(n, m, x, y\) (1-indexed) where \(n\) and \(m\) are the dimensions of the matrix and \(x, y\) specify the query cell.

Each of the next \(n\) lines contains \(m\) integers representing the matrix \(a\), where the \(j\)th integer in the \(i\)th line is \(a_{i,j}\).

outputFormat

Output a single integer: the minimum number of transformations needed so that \(a_{x,y}\) becomes 1. If it is impossible, output \(-1\).

sample

2 2 1 1
2 3
4 1

1