P16343 [KUST Innovation Cup Junior 2026] Walking

Subtask 0 uses community testdata, and Subtask 1 uses official testdata.

Xiaokeke has an $n \times n$ grid. Cell $(i, j)$ contains a positive integer $a_{i,j}$. Xiaokeke wants to walk from $(1, 1)$ to $(n, n)$. He can only move down or right, that is, from $(i, j)$ to $(i+1, j)$ or from $(i, j)$ to $(i, j+1)$. He has a positive integer $v$, initially $a_{1,1}$. Each time Xiaokeke arrives at a cell $(i, j)$, $v$ becomes $\gcd(v, a_{i,j})$. Xiaokeke wants to know the maximum possible value of $v$ when he reaches $(n, n)$. > $\gcd(i, j)$ denotes the greatest common divisor of positive integers $i$ and $j$, i.e., the largest positive integer $d$ such that $d$ divides $i$ and $d$ divides $j$.

The input has a total of $n+1$ lines. - The first line contains two positive integers $n, V$. - Lines $2$ to $n+1$ each contain $n$ positive integers. The $j$-th number on line $i+1$ represents $a_{i,j}$.

Output one line containing one positive integer, representing the answer.

#### Sample Explanation Xiaokeke’s optimal route is $(1, 1) \to (2, 1) \to (2, 2)$. #### Other Sample Notes - **Samples 2 to 5**: see `walk/walk*.in` and `walk/walk*.ans` in the contestant directory. #### Constraints For all data, it is guaranteed that: - $1 \le n \le 1000$. - $1 \le a_{i,j} \le V \le 10000$. - All input numbers are positive integers. | Test Point ID | $n \le$ | $a_{i,j}, V \le$ | Special Property | | :---: | :---: | :---: | :---: | | $1, 2, 3$ | $10$ | $10000$ | None | | $4, 5, 6$ | $100$ | $100$ | None | | $7, 8$ | $1000$ | $10000$ | The data is guaranteed to be random | | $9, 10$ | $1000$ | $10000$ | None | Translated by ChatGPT 5