Arrow Grid Game

BaoBao has found a grid with \(n\) rows and \(m\) columns. In each cell \((i, j)\) (where \(1 \le i \le n\) and \(1 \le j \le m\)), there is an arrow (which points either upwards, downwards, leftwards or rightwards) and an integer \(a_{i,j}\). When BaoBao ticks a cell, he then moves to another cell according to the following rule:

• If the arrow in cell \((i, j)\) points upwards (^), he moves to cell \((i - a_{i,j}, j)\) if it exists.
• If it points downwards (v), he moves to cell \((i + a_{i,j}, j)\) if it exists.
• If it points leftwards (<), he moves to cell \((i, j - a_{i,j})\) if it exists.
• If it points rightwards (>), he moves to cell \((i, j + a_{i,j})\) if it exists.

The game starts by choosing an initial cell and ticking it. Then, following the rule above, BaoBao ticks subsequent cells. The game stops if the next cell does not exist or has already been ticked. Your task is to determine whether there exists an initial cell such that by following these moves, every cell in the grid is ticked exactly once before the game terminates.

inputFormat

The input consists of:

1. A line containing two integers \(n\) and \(m\) representing the number of rows and columns respectively.
2. Then follow \(n\) lines, each containing a string of length \(m\). Each character in the string is one of ^, v, <, or >, representing the direction of the arrow in that cell.
3. Finally, there are \(n\) lines, each containing \(m\) integers. The \(j\)-th integer in the \(i\)-th line is \(a_{i,j}\), the step size for cell \((i, j)\).

outputFormat

Output a single line: YES if there exists an initial cell that by following the rules ticks every cell exactly once; otherwise, output NO.

sample

2 2
>v
^<
1 1
1 1

YES