AT_past202303_g 隣り合うマス

There is a grid with $ H $ horizontal rows and $ W $ vertical columns. The square at the $ i $ -th row from the top and $ j $ -th column from the left has a number $ A_{i,j} $ written on it. $ A_{i,j} $ are distinct integers between $ 1 $ and $ HW $ . Find all the integer pairs $ (x,y) $ satisfying $ 1\leq x < y \leq HW $ such that the square with $ x $ written on it is adjacent to the one with $ y $ . A square is said to be adjacent to another if these two squares share a side.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ A_{1,1} $ $ \ldots $ $ A_{1,W} $ $ \vdots $ $ A_{H,1} $ $ \ldots $ $ A_{H,W} $

Let $ K $ be the number of integer pairs $ (x,y) $ satisfying $ 1\leq x < y \leq HW $ such that the square with $ x $ written on it is adjacent to the one with $ y $ . Print $ K $ lines. The $ i $ -th line should contain $ x $ and $ y $ for the $ i $ -th lexicographically smallest such pair, separated by a space.

### Sample Explanation 1 The square with $ 1 $ written on it is adjacent to the one with $ 2 $ . ### Constraints - $ 1 \leq H,W $ - $ 2 \leq H \times W \leq 2\times 10^5 $ - $ 1 \leq A_{i,j} \leq H \times W $ - $ H $ and $ W $ are integers. - $ A_{i,j} $ are distinct integers.