题目背景

本题为原创。灵感来源于 2026 年科大国创杯初中组 T3。

题目描述

给定一个 $n \times m$ 大小的网格图，小 A 初始站在网格图的左上角 $(1, 1)$ 位置。对于从点 $(x,y)$ 开始的每次移动，小 A 可以选择向下或向右移动一个单位长度到达 $(x+1, y)$ 或 $(x, y+1)$ ，或者向右下方移动 $\sqrt{2}$ 个单位长度（对角线）到达 $(x+1, y+1)$。每个点 $(i, j)$ 都有格权重 $a_{i,j}$。小 A 手中有一个数 $V$，初始值为 $a_{1,1}$，每次移动到 $(x', y')$，$V$ 就变成 $\operatorname{lcm}(V, a_{x', y'})$，其中 $\operatorname{lcm}(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数。

现给出图上每个点的格权重，试求一种移动方式使得移动到点 $(n, m)$ 时，小 A 手中的 $V$ 值最小。

输入格式

输入包含 $n+1$ 行。

第一行包含两个正整数 $n$ 和 $m$，含义如题目所示。

随后 $n$ 行，每行包含 $m$ 个整数。第 $i+1$ 行第 $j$ 个整数代表点 $(i, j)$ 的格权重 $a_{i,j}$。

输出格式

输出一个正整数，代表移动到 $(n, m)$ 处时可能的最小的 $V$ 值。

数据范围

$1 \leq n, m \leq 1000$，$1 \leq a_{i,j} \leq 15$。