So, Mr. Intelligent, have you played the game Red Dead Redemption 2? Yeah, man, this game deserves a Heavenly place in the hearts of gamers.

Our hero Arthur Morgan is now on Newyork city in the modern civilization of America. As always, he is now being chased by some Cops. As the civilization has developed a lot, now there are a lots of Police Stations in different places of Newyork. And there are also a lots of buildings and shopping malls spreading all around the city. Besides there are also some docks from which our hero Arthur can get out of the New America as well as escaping from the cops. There are some roads in between all the obstacles of the city which will lead our hero to any docks from which he can escape.

In this problem, we will consider Newyork city as an N × M matrix. Where each police station is denoted as the letter 'S' and the roads are considered as '.'. And whenever you find the character '#', that means nobody can get through this as it is an obstacle. Arthur and the Cops can only travel through the roads. Each Police Station contains exactly one cop. Each one cop will start his journey from a police station and will move along the road. And by any means, if our hero Arthur can get to any border of the given matrices without being caught by the cops, that means, he has escaped. Remember, that border should not contain any obstacle nor any police station.

You're given the initial position of Arthur ('A'). Note that, the cops can start their journey from any police station and can also move only along the roads. Arthur has to move in such a way that, there are no cops at that time when he get through that certain point of road.

Now, as being an intelligent companion of Arthur, you have to tell, if it is possible to get out of the New America. If it is possible, you have to tell the path which Arthur should follow and the length of that path.

Constraints

• 1 ≤ n, m ≤ 1000

Input

The first input line has two integers n and m: the height and width of the map.

After this there are n lines of m characters describing the map. Each character is . (road), # (obstacles), A (starting position of Arthur), or S (Police Stations). There is exactly one A in the input.

Output

First print "YES" if your goal is possible, and "NO" otherwise.

If your goal is possible, also print an example of a valid path (the length of the path and its description using characters D, U, L, and R). You have to print the shortest path, as long as its length is at most n × m steps.

Sample

Input 1:
4 4
#.#S
#.##
#A..
####

Output 1:
YES
2
UU

Input 2:
4 4
#..S
#.##
#A.#
####

Output 2:
NO