ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1589. Sokoban

Time limit: 5.0 second
Memory limit: 64 MB
For the period of his vacation, programmer Stas found a job with the Japanese computer company Thinking Rabbit. At first glance, the idea seemed marvelous: he would go abroad, earn some money, and learn from his Japanese colleagues. However, it turned out that the company did not want programmers without good knowledge of Japanese. Therefore, Stas was sent to work as a storekeeper (in Japanese, this profession was called soko-ban).
Stas had to put the storehouse to order. Every morning he was given a sheet of paper with a scheme of the room in the storehouse where he had to work that day. The scheme showed the places where he had to put containers. For some reason, the management of the company did not bother about which container would be put to which place; they only wanted all containers to be put to the places marked on the scheme.
The task was not easy. The containers were large and heavy; it was only possible to move them by pushing along the floor, and they were too heavy to push more than one of them at a time. In addition, the containers were so smooth that Stas could not pull or turn them; all he could do was to push them forward in front of him. The dimensions of the room corresponded to the size of containers exactly, so Stas could not clime over a container, squeeze himself between containers, or wriggle himself between a container and a wall. He could only move through unoccupied space. Thus, putting containers in order was a tricky puzzle. And if Stas could not solve it or put incidentally one of the containers into some corner from which it could not be extracted, then Stas was in real trouble. The point was that the walls of the room were solid, with no exits. In the morning, Stas got to the room through one of the hatches in the ceiling. He could not leave the room until the task was completed. When all containers were on their places, the smart control system opened a hatch with a rope-ladder for Stas right over him.
Help Stas to make a plan of moving the containers.


You are given a scheme of the storeroom. This is a table of size n × m (3 ≤ n, m ≤ 8). An empty cell is shown by a space, and objects are denoted as follows:
  • # is a piece of wall
  • . is an empty cell where a container must be put (an aim cell)
  • @ is the cell from which Stas starts his work if it is not an aim cell
  • + is the cell from which Stas starts his work if it is an aim cell
  • $ is a container on a cell which is not an aim cell
  • * is a container on an aim cell
It is guaranteed that the scheme of the room is correct, that is, Stas cannot go out of the room. The number of containers is equal to the number of aim cells.


Output a plan of work for Stas. In a single line, you should specify his movements by letters r, l, u, and d, which correspond to the four possible directions of moves. If during a move a container is pushed, then the letters should be capital (R, L, U, and D, respectively). The string should be no longer than 10000 symbols. You may assume that there is a solution.


#@  $ .#
##   .#
#@  ###
#   * #
#   $ #
#     #
Problem Author: Stanislav Vasilev and Sergey Pupyrev
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007