using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 5");
WillReturn.Add(".#...");
WillReturn.Add(".Sooo");
WillReturn.Add("..x.G");
//Yes
//DRUUDDRR
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 3");
WillReturn.Add("#So");
WillReturn.Add("xoG");
WillReturn.Add("..#");
//Yes
//DDLURR
}
else if (InputPattern == "Input3") {
WillReturn.Add("2 2");
WillReturn.Add("So");
WillReturn.Add("oG");
//No
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
static char[,] mBanArr;
static long UB_X;
static long UB_Y;
static long mStaX;
static long mStaY;
static long mGoalX;
static long mGoalY;
static Dictionary<long, long> mParentHashDict = new Dictionary<long, long>();
static void Main()
{
List<string> InputList = GetInputList();
mBanArr = CreateBanArr(InputList.Skip(1));
UB_X = mBanArr.GetUpperBound(0);
UB_Y = mBanArr.GetUpperBound(1);
for (long X = 0; X <= UB_X; X++) {
for (long Y = 0; Y <= UB_Y; Y++) {
if (mBanArr[X, Y] == 'S') {
mStaX = X;
mStaY = Y;
}
if (mBanArr[X, Y] == 'G') {
mGoalX = X;
mGoalY = Y;
}
}
}
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.CurrX = mStaX;
WillEnqueue.CurrY = mStaY;
WillEnqueue.VectX = 0;
WillEnqueue.VectY = 0;
WillEnqueue.Level = 0;
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<long>();
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
long CurrX = Dequeued.CurrX;
long CurrY = Dequeued.CurrY;
long VectX = Dequeued.VectX;
long VectY = Dequeued.VectY;
long ParentHash = GetHash(CurrX, CurrY, VectX, VectY);
// 枝切り
if (Dequeued.Level > 5 * 1000000) continue;
if (Dequeued.CurrX == mGoalX && Dequeued.CurrY == mGoalY) {
KeiroHukugen(ParentHash);
return;
}
Action<long, long, long, long> EnqueueAct = (pNewX, pNewY, pNewVectX, pNewVectY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
if (mBanArr[pNewX, pNewY] == '#') return;
long CurrHash = GetHash(pNewX, pNewY, pNewVectX, pNewVectY);
if (VisitedSet.Add(CurrHash)) {
mParentHashDict[CurrHash] = ParentHash;
WillEnqueue.CurrX = pNewX;
WillEnqueue.CurrY = pNewY;
WillEnqueue.VectX = pNewVectX;
WillEnqueue.VectY = pNewVectY;
WillEnqueue.Level = Dequeued.Level + 1;
Que.Enqueue(WillEnqueue);
}
};
if (mBanArr[CurrX, CurrY] == 'o') {
EnqueueAct(CurrX + VectX, CurrY + VectY, VectX, VectY);
}
if (mBanArr[CurrX, CurrY] == 'x') {
bool Bool1 = (VectX == 0 && VectY == -1);
bool Bool2 = (VectX == 0 && VectY == +1);
bool Bool3 = (VectX == -1 && VectY == 0);
bool Bool4 = (VectX == +1 && VectY == 0);
if (Bool1 == false) EnqueueAct(CurrX, CurrY - 1, 0, -1);
if (Bool2 == false) EnqueueAct(CurrX, CurrY + 1, 0, +1);
if (Bool3 == false) EnqueueAct(CurrX - 1, CurrY, -1, 0);
if (Bool4 == false) EnqueueAct(CurrX + 1, CurrY, +1, 0);
}
if (mBanArr[CurrX, CurrY] == '.' || mBanArr[CurrX, CurrY] == 'S') {
EnqueueAct(CurrX, CurrY - 1, 0, -1);
EnqueueAct(CurrX, CurrY + 1, 0, +1);
EnqueueAct(CurrX - 1, CurrY, -1, 0);
EnqueueAct(CurrX + 1, CurrY, +1, 0);
}
}
Console.WriteLine("No");
}
// 経路復元して出力
static void KeiroHukugen(long pGoalHash)
{
long CurrX;
long CurrY;
long VectX;
long VectY;
GetJyoutai(pGoalHash, out CurrX, out CurrY, out VectX, out VectY);
long CurrHash = pGoalHash;
var AnswerList = new List<char>();
while (true) {
CurrHash = mParentHashDict[CurrHash];
char Answer = DeriveChar(VectX, VectY);
AnswerList.Add(Answer);
GetJyoutai(CurrHash, out CurrX, out CurrY, out VectX, out VectY);
if (CurrX == mStaX && CurrY == mStaY) break;
}
var sb = new System.Text.StringBuilder();
sb.AppendLine("Yes");
AnswerList.Reverse();
AnswerList.ForEach(pX => sb.Append(pX));
sb.AppendLine();
Console.Write(sb.ToString());
}
// 移動元と移動先を引数として、移動文字を返す
static char DeriveChar(long pVectX, long pVectY)
{
if (pVectX == -1) return 'L';
if (pVectX == +1) return 'R';
if (pVectY == -1) return 'U';
if (pVectY == +1) return 'D';
throw new Exception("例外");
}
struct JyoutaiDef
{
internal long CurrX;
internal long CurrY;
internal long VectY;
internal long VectX;
internal long Level;
}
static long GetHash(long pX, long pY, long pVectX, long pVectY)
{
long Hash = 0;
Hash += pX;
Hash *= 10000;
Hash += pY;
Hash *= 10;
Hash += pVectX + 2;
Hash *= 10;
Hash += pVectY + 2;
return Hash;
}
static void GetJyoutai(long pHash, out long pCurrX, out long pCurrY, out long pVectX, out long pVectY)
{
pVectY = pHash % 10;
pHash /= 10;
pVectX = pHash % 10;
pHash /= 10;
pCurrY = pHash % 10000;
pHash /= 10000;
pCurrX = pHash;
pVectY -= 2;
pVectX -= 2;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をcharの2次元配列に設定
////////////////////////////////////////////////////////////////
static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new char[0, 0];
}
int UB_X = StrList[0].Length - 1;
int UB_Y = StrList.Count - 1;
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = StrList[Y][X];
}
}
return WillReturn;
}
}