F. Anomia
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Anomia neighborhood, there is a fugitive wanted by the police. To capture him, the police have stationed several officers at fixed locations throughout the neighborhood to monitor the area.

The neighborhood is represented as an $$$N \times M$$$ grid of characters, where each cell can be one of the following:

- '.': a road

- '#': a building

- 'F': the initial location of the fugitive

- 'H': the fugitive's hideout

- '$$$ \gt $$$', '$$$ \lt $$$', '$$$^{\wedge}$$$', 'v': a police officer positioned at a fixed location and looking in a specific direction (right, left, up, down respectively)

Each police officer monitors the cells in their line of sight, defined by the direction they are facing and a maximum distance $$$D$$$. A police officer's line of sight is blocked by buildings and other police officers.

The fugitive can only move right, left, up and down, not diagonally.

Your task is to determine if there is a safe path for the fugitive to move from his initial location to his hideout without being seen by any police officer.

Input

The first line gives you three space-separated integers: the grid's number or rows $$$N$$$, the grid's number of columns $$$M$$$ and the line of sight distance $$$D$$$.

The next $$$N$$$ lines contain $$$M$$$ characters that represent the neighborhood map.

Output

The string 'YES' if there is a safe path to the hideout, otherwise the string 'NO'.

Example
Input
4 7 100
...F...
>...##.
.....#.
...H...
Output
YES
Note

Limits

- $$$1 \leq N, M \leq 1000$$$

- $$$1 \leq D \leq 1000$$$