Your friend has discovered a "100% unpatched unlimited free money method" and has quickly become a "Tall Poppy" in the office. Now, he is being targeted by jealous coworkers and needs your help to make a quick exit without running into anyone.

Since his coworkers are too lazy to move, their positions are completely stationary. You have been given a grid map of the building indicating all walls, empty spaces, coworkers, and exits.

Your task is to determine whether it is possible for the Tall Poppy to reach at least one exit by moving horizontally or vertically through open spaces.

Movement Rules

• $: The Tall Poppy's starting position.
• E: An exit.
• .: An empty square.
• *: A stationary coworker.
• #: A wall.
• Movement is permitted in four directions: Up, Down, Left, and Right, so long as there is an empty square or exit in that direction.
• The Tall Poppy may not move outside the confines of the office.

Input

The first line contains two space-separated integers ~R, C~ (~1 \le R, C \le 1000~) representing the number of rows and columns in the building grid.

The following ~R~ lines each contain a string of ~C~ characters describing the row's map layout, as detailed above.

The grid contains exactly one starting position ($).

The grid contains at least one exit (E).

Output

Output YES if there is a valid path from the Tall Poppy ($) to any exit (E). Output NO if no valid path exists.

Example

Input 1

5 5
#####
#$..#
#*#.#
#..E#
#####

Output 1

YES

Explanation: The Tall Poppy ($) can move right along row 2, down column 4, and step onto the exit (E) at position (4, 4), avoiding all walls and coworkers.

Input 2

4 4
####
#$*E
#*#*
####

Output 2

NO

Explanation: All paths leading away from the starting position ($) are blocked by coworkers (*) or walls (#), making it impossible to reach the exit.

Input 3

1 2
$E

Output 3

YES

Explanation: The Tall Poppy starts at position (1, 1) and moves directly right into position (1, 2), reaching the exit in a single step.