A prisoner is trying to escape from a prison while several guards patrol the area. At each step, the prisoner can move to an adjacent cell, and simultaneously, each guard can also move to an adjacent cell. The objective is for the prisoner to reach any boundary cell of the prison without ever sharing a cell with a guard.

The task is to determine whether such an escape is possible. If it is, print an escape path the prisoner can follow. The escape plan must succeed in every scenario, even if the guards know the prisoner's path in advance and act accordingly.

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 1000)$$$ — the height and width of the prison grid.

The following $$$n$$$ lines each contain $$$m$$$ characters describing the prison layout:

• . — empty corridor cell
• # — wall (impassable)
• A — prisoner's initial position
• G — guard's initial position

The grid contains exactly one A. There may be zero or more G characters.

Print YES if escape is possible; otherwise, print NO.

If escape is possible, additionally print:

• First line: an integer $$$k$$$ — the number of moves in the escape path
• Second line: a string of length $$$k$$$ consisting of characters U, D, L, R representing the sequence of moves (up, down, left, right)

You can print any path, as long as its length is at most $$$n \cdot m$$$ steps.

In the first test case, the prisoner starts at position $$$(2,5)$$$ and can reach the boundary at $$$(4,8)$$$ by following the path RRDDR.