Escape Room

Interview

Time limit2sMemory limit512 MB

Summary

Given an M by N grid of integers, start at (1,1) and jump from cell value x to any cell (a,b) with a*b=x, staying inside the grid; decide if (M,N) is reachable.

Level: Medium5 of 10
Topics: Graph, BFS, Number theory, Math
Solved: No attempts yet

Problem

You have to determine if it is possible to escape from a room. The room is an M-by-N grid with each position (cell) containing a positive integer. The rows are numbered 1, 2, ..., M and the columns are numbered 1, 2, ..., N. We use (r, c) to refer to the cell in row r and column c.

You start in the top-left corner at (1, 1) and exit from the bottom-right corner at (M, N). If you are in a cell containing the value x, then you can jump to any cell (a, b) satisfying a × b = x. For example, if you are in a cell containing a 6, you can jump to cell (2, 3).

Note that from a cell containing a 6, there are up to four cells you can jump to: (2, 3), (3, 2), (1, 6), or (6, 1). If the room is a 5-by-6 grid, there isn't a row 6 so only the first three jumps would be possible.

Input

The first line of the input will be an integer M (1 ≤ M ≤ 1000). The second line of the input will be an integer N (1 ≤ N ≤ 1000). The remaining input gives the positive integers in the cells of the room with M rows and N columns. It consists of M lines where each line contains N positive integers, each less than or equal to 1 000 000, separated by single spaces.

Output

Output yes if it is possible to escape from the room. Otherwise, output no.

Examples1

Example 1
Input
```
3
4
3 10 8 14
1 11 12 12
6 2 3 9
```
Expected output
```
yes
```