Voyager 1

Interview

Time limit1sMemory limit128 MB

Summary

From a starting cell, fire a beam in each of four directions through mirrors / and \, black holes C, and empty cells, and report which direction survives longest or detect an infinite loop.

Level: Medium5 of 10
Topics: Simulation, Implementation, Graph, Matrix
Solved: No attempts yet

Problem

Voyager 1 is NASA's unmanned interplanetary probe, launched in 1977. It is currently in the heliosheath.

A long-lived probe like Voyager 1 records its route by radio signal every time it meets a star system.

Think of a star system as an $N$ -row by $M$ -column rectangular grid. Each cell may hold a planet or a black hole, or be empty. The probe picks one of the four adjacent directions (up, down, left, right) and sends a signal.

The signal always travels in a straight line, and when it meets a planet its direction turns by 90 degrees. There are two kinds of planets, written / and \, whose reflection rules are shown below.

The signal keeps traveling until it meets a black hole or leaves the star system. It spends one second in each cell it passes through, so the time the signal stays inside the star system equals the number of cells it passes through, counting the probe's own cell (a black hole stops the signal and is not counted).

Write a program that finds which direction the probe should send the signal so that the signal stays inside the star system for as long as possible.

Input

The first line contains $N$ and $M$ . ( $1 \le N, M \le 500$ )

Each of the next $N$ lines contains $M$ characters. / and \ denote planets, C denotes a black hole, and . denotes an empty cell.

The last line contains the probe's position $PR$ and $PC$ . ( $1 \le PR \le N$ , $1 \le PC \le M$ )

Output

On the first line, output the direction to send the signal. (U: up, R: right, D: down, L: left.) If several directions give the longest time, output the one that comes first in the order U, R, D, L.

On the second line, output the longest time. If the signal can travel forever inside the star system, output Voyager.

Hint

The reflection rules are: / swaps up↔right and down↔left, while \ swaps up↔left and down↔right.

If the signal ever passes through the same cell heading in the same direction again, it can never leave the star system and will circulate forever. In that case the time for that direction is infinite and is printed as Voyager.

Examples3

Example 1

Input

5 5
../.\
.....
.C...
...C.
\.../
3 3

Expected output

U
17

Example 2

Input

5 5
....\
\..\.
./\..
\../C
.\../
1 1

Expected output

D
12

Example 3

Input

5 7
/.....\
../..\.
\...../
/.....\
\.\.../
3 3

Expected output

R
Voyager