Optimally solve the Flux Puzzle Flux is very similar to the Fifteen Puzzle.

However, instead of numbers, the squares are colors.


There are 4 colors: Red, Yellow, Blue, and Gray.


There are exactly 4 red squares, 4 yellow squares, 2 blue squares, 1 gray square, and 1 empty square.

The grid has 3 rows and 4 columns
A grid configuration is solved when the top row is exactly the same as the bottom row.
The middle row is not relevant when considering whether the board is solved.
You do not have to handle invalid input. Trust that there will be the correct number of each of the input symbols.


Input


You must accept an input of twelve of these characters that use these symbols to represent a square on the board:


RYGB_

These input characters must be interpreted to go across, then down.
It is your choice whether you require some other character (newline, EOF, whatever) to terminate input, or just go as soon as you've received 12 characters.


Example:

YRGYB_BRRYYR


which corresponds to to the board:

YRGY
B_BR
RYYR


Output


You must output the moves required for an OPTIMAL solution
These will use the characters LRUD for Left, Right, Up, Down. This is considered to be the "piece moves to the left", not the "emptiness moves to the left"


Example:

LURDRDLULDLU


And then print out the resulting board. For the example we've used so far:

RBYR
YYG_
RBYR


Other rules


Your program must run in under 15 seconds or it is disqualified.


Make sure to try it with the following board: RRRRBG_BYYYY
That board, with it's three symmetries, is the "hardest" possible board.

You may not use any external resources, or have any input data files.


Some stats


There are exactly 415,800 possible boards
There are exactly 360 "solution" boards
My program that I wrote to test this out runs in about 2 seconds in Java, without much optimization.


This program, with minimal golfing, is 1364 bytes.



Scoring


This is code-golf, fewest characters that meets the other requirements wins!
Smalltalk 497
|b R M s g a|
b:=Stdin nextLine.R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)(1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)(6 1)(4 6 1)(4 6 1)(4 1)).
s:=Set new.q:=OrderedCollection new.
a:=[:p :m|(s includes:p)ifFalse:[s add:p.q add:p-&gt;m]].
a value:b value:''.
[|x i n p|
x:=q removeFirst.p:=x key.i:=(p indexOf:$_).
(M at:i)do:[:m||v|
n:=p copy.n at:i put:(p at:i+m-5);at:i+m-5put:$_.
v:=(x value,(R at:m)).
(n to:4)=(n from:9)ifTrue:[
v printCR.(n splitForSize:4)map:#printCR.^self].
a value:n value:v]]loop.

Input:
YRGYB_BRRYYR

Output:
DLURRULDDLLU
YBYR
RGR_
YBYR

Exec. Time (bytecode, not jitted): 100ms
Input:
RRRRBG_BYYYY

Output:
DRRUULLDLURDDRRULULD
YBRR
GY_Y
YBRR

Exec. Time 2s unjitted; 0.8s jitted (most time spent in collection code)
Here is an ungolfed version for readability:
|b R M s g add|
b:=Stdin nextLine.
R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)
     (1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)
     (6 1)(4 6 1)(4 6 1)(4 1)).
s := Set new.
queue := OrderedCollection new.

add := [:p :m |
  (s includes:p) ifFalse:[
    s add:p.
    queue add:(p-&gt;m).
  ]].

add value:b value:''.

[
  |x i n p|

  x := queue removeFirst.
  p := x key.
  i := (p indexOf:$_).
  (M at:i) do:[:m |
    |v|
    n := p copy.
    n at:i put:(p at:i+m-5); at:i+m-5 put:$_.
    v:=(x value,(R at:m)).
    (n to:4)=(n from:9) ifTrue:[
      v printCR.
      (n splitForSize:4) map:#printCR.
      ^ self
    ].
    add value:n value:v]
] loop.