#include <iostream>
#include <vector>
#include <cstdint>
#include <unordered_map>
#include <set>
#include <queue>
#include <cmath>

template <int size>
class Board {
public:
    struct State {
        State() = default;

        State(uint64_t state, size_t zero_index, size_t width, size_t turn_number);

        State(const std::vector<size_t>& combinations, size_t width, size_t turn_number);

        bool operator== (const State& rhv);

        size_t Get(size_t index) const;

        void Set(size_t index, size_t number);

        bool CanMoveUp() const;

        bool CanMoveDown() const;

        bool CanMoveRight() const;

        bool CanMoveLeft() const;

        State MoveUp() const;

        State MoveDown() const;

        State MoveLeft() const;

        State MoveRight() const;

        uint64_t GetState() const;

        size_t GetEstimate() const;
        size_t width_;
        size_t number_of_turn;
        void show() {
            for (auto i = 0; i < size - 1; ++i) {
                std::cout << Get(i) << " ";
            }
            std::cout << std::endl;
        }
    private:
        uint64_t state_ = 0;
        size_t zero_index_;

        static const std::vector<uint64_t> masks_;
        static const std::vector<uint64_t> anti_masks_;
    };

    struct Estimation {
        size_t estimation_;
        State state_;
        Estimation(State state);
    };

    struct Cmp {
        bool operator() (const Estimation& lhv, const Estimation& rhv) const;
    };

    bool ExistSolution(std::vector<size_t > positions) const;  // Проверяет существование решения (служебная)

    State source_;   // изначальная конфигурация доски
    State target_;    // конфигурация финиша
    std::unordered_map<uint64_t , std::pair<uint64_t , int>> parents_;
    size_t board_width_;
    bool have_solution_;
public:
    Board(const std::vector<size_t>& positions);

    std::vector<State> GetNext(State vertex) const;  //  Возвращает всевозможные расстановки чисел, получаемые
                                                       // из исходного положения выполнением хода
    bool HaveSolution();   // Проверяет существование решения (публичная)

    std::pair<int, std::vector<char>> FindWinningConfiguration();

    std::pair<int, std::vector<char>> ToSolvePuzzle();

};


int main() {
    const int size = 16;
    std::vector<size_t> combination;
    for (auto i = 0; i < size; ++i) {
        size_t number;
        std::cin >> number;
        combination.push_back(number);
    }
    Board<size> board(combination);
    if (!board.HaveSolution()) {
        std::cout << -1;
    }
    else {
        std::pair<size_t, std::vector<char>> game_solution;
        game_solution = board.ToSolvePuzzle();
        std::cout << game_solution.first << std::endl;
        for (auto movement : game_solution.second) {
             std::cout << movement;
        }
    }
    return 0;
}



template <int size>
std::pair<int, std::vector<char>> Board<size>::ToSolvePuzzle() {
    std::multiset<Estimation, Cmp> estimations;
    estimations.insert(Estimation(source_));
    bool find = false;
    while (!find) {
        State current_vertex = estimations.begin()->state_;
        estimations.erase(estimations.begin());
        std::vector<State> next_vertices = GetNext(current_vertex);
        for (auto i = 0; i < next_vertices.size(); ++i) {
            if (next_vertices[i] == target_) {
                find = true;
                parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
            }
            else if (next_vertices[i].GetState() != 0 && parents_.find(next_vertices[i].GetState()) == parents_.end()) {
                estimations.insert(Estimation(next_vertices[i]));
                parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
            }
        }
    }
    size_t distance = 0;
    std::vector<int> steps;
    std::vector<char> movements;
    State current_vertex(target_.GetState(), 0, board_width_, 0);
    while (parents_[current_vertex.GetState()].first != 0) {   // по предкам поднимаемся до исходной конфигурации,
        distance += 1;                                         // попутно увеличивая дистанцию и запоминая переходы
        steps.push_back(parents_[current_vertex.GetState()].second);
        current_vertex = State(parents_[current_vertex.GetState()].first, 0, board_width_, 0);
    }
    for (int i = static_cast<int>(steps.size()) - 1; i >= 0; --i) {    // обработка переходов
        if (steps[i] == 0) {
            movements.push_back('U');
        }
        else if (steps[i] == 1) {
            movements.push_back('D');
        }
        else if (steps[i] == 2) {
            movements.push_back('R');
        }
        else {
            movements.push_back('L');
        }
    }
    return {distance, movements};

}

template <int size>
Board<size>::Estimation::Estimation(Board<size>::State state) {
    state_ = state;
    std::vector<size_t> table;
    size_t manhattan_distance = 0;
    for (auto i = 0; i < size; ++i) {
        table.push_back(state.Get(i));
    }
    for (auto i = 0; i < size; ++i) {
        if (table[i] != 0) {
            size_t row = i / state.width_;
            size_t column = i % state.width_;
            size_t diff_x = abs((table[i] - 1) / state.width_ - row);
            size_t diff_y = abs((table[i] - 1) % state.width_ - column);
            manhattan_distance += diff_x + diff_y;
        }
    }
    estimation_ = manhattan_distance;
}

template <int size>
bool Board<size>::Cmp::operator()(const Board<size>::Estimation &lhv, const Board<size>::Estimation &rhv) const {
    return lhv.estimation_ < rhv.estimation_;
}

template <int size>
size_t Board<size>::State::GetEstimate() const {   std::vector<size_t> table;
    size_t manhattan_distance = 0;
    for (auto i = 0; i < size; ++i) {
        table.push_back(Get(i));
    }
    for (auto i = 0; i < size; ++i) {
        if (table[i] != 0) {
            size_t row = i / width_;
            size_t column = i % width_;
            size_t diff_x = abs((table[i] - 1) / width_ - row);
            size_t diff_y = abs((table[i] - 1) % width_ - column);
            manhattan_distance += diff_x + diff_y;
        }
    }
    return manhattan_distance + number_of_turn;

}

template <int size>
std::pair<int, std::vector<char>> Board<size>::FindWinningConfiguration() {
    std::queue<State> vertices;
    vertices.push(source_);
    bool find = false;
    uint64_t target_state;
    while (!find) {                  // идем BFS'ом, пока не наткнемся на победную конфигурацию
        State current_vertex = vertices.front();
        vertices.pop();
        std::vector<State> next_vertices = GetNext(current_vertex);
        for (int i = 0; i < next_vertices.size(); ++i) {
            if (next_vertices[i] == target_) {
                find = true;
                target_state = next_vertices[i].GetState();
                parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
            }
            if (next_vertices[i].GetState() != 0 && parents_.find(next_vertices[i].GetState()) == parents_.end()) {
                vertices.push(next_vertices[i]);
                parents_[next_vertices[i].GetState()] = {current_vertex.GetState(), i};
            }
        }
    }
    size_t distance = 0;
    std::vector<int> steps;
    std::vector<char> movements;
    State current_vertex(target_state, 0, board_width_, 0);
    while (parents_[current_vertex.GetState()].first != 0) {   // по предкам поднимаемся до исходной конфигурации,
        distance += 1;                                         // попутно увеличивая дистанцию и запоминая переходы
        steps.push_back(parents_[current_vertex.GetState()].second);
        current_vertex = State(parents_[current_vertex.GetState()].first, 0, board_width_, 0);
    }
    for (int i = static_cast<int>(steps.size()) - 1; i >= 0; --i) {    // обработка переходов
        if (steps[i] == 0) {
            movements.push_back('D');
        }
        else if (steps[i] == 1) {
            movements.push_back('U');
        }
        else if (steps[i] == 2) {
            movements.push_back('L');
        }
        else {
            movements.push_back('R');
        }
    }
    return {distance, movements};
}

template <int size>
bool Board<size>::HaveSolution() {
    return have_solution_;
}

template <int size>
bool Board<size>::ExistSolution(std::vector<size_t> positions) const {
    std::vector<size_t> sequence_checker;
    std::vector<size_t> subsequence;
    size_t i = 0;
    size_t row = 1;                                      // организация исходного массива расстановки
    size_t zero_ind = 0;                                 // в расстановку змейкой для определения количества инверсий
    size_t inversions = 0;
    while (sequence_checker.size() != positions.size()) {
        while (subsequence.size() != board_width_) {
            subsequence.push_back(positions[i]);
            i += 1;
        }
        if (row % 2) {
            for (auto j = 0; j < board_width_; ++j) {
                sequence_checker.push_back(subsequence[j]);
                if (sequence_checker[sequence_checker.size() - 1] == 0) {
                    zero_ind = sequence_checker.size() - 1;
                }
            }
        }
        else {
            for (int j = static_cast<int>(subsequence.size()) - 1; j >= 0; --j) {
                sequence_checker.push_back(subsequence[j]);
                if (sequence_checker[sequence_checker.size() - 1] == 0) {
                    zero_ind = sequence_checker.size() - 1;
                }
            }
        }
        row += 1;
        subsequence.clear();
    }
    for (auto j = zero_ind; j < sequence_checker.size(); ++j) {
        if (zero_ind == sequence_checker.size() - 1) {
            break;
        }
        else {
            sequence_checker[j] = sequence_checker[j + 1];
        }
    }
    for (auto j = 0; j < sequence_checker.size() - 1; ++j) {         // подсчет инверсий
        for (auto p = j; p < sequence_checker.size() - 1; ++p) {
            if (sequence_checker[j] > sequence_checker[p]) {
                inversions += 1;
            }
        }
    }
    return static_cast<bool>((inversions % 2));
}

template <int size>
std::vector<class Board<size>::State> Board<size>::GetNext(Board<size>::State vertex) const {
    std::vector<class Board<size>::State> next_vertices;   // если какое-либо движение невыполнимо, то возвращаем пустышку
    (vertex.CanMoveDown()) ? next_vertices.push_back(vertex.MoveDown()) : next_vertices.push_back(State(0, 0, board_width_, 0));
    (vertex.CanMoveUp()) ? next_vertices.push_back(vertex.MoveUp()) : next_vertices.push_back(State(0, 0, board_width_, 0));
    (vertex.CanMoveLeft()) ? next_vertices.push_back(vertex.MoveLeft()) : next_vertices.push_back(State(0, 0, board_width_, 0));
    (vertex.CanMoveRight()) ? next_vertices.push_back(vertex.MoveRight()) : next_vertices.push_back(State(0, 0, board_width_, 0));
    return next_vertices;
}

template <int size>
bool Board<size>::State::operator==(const class Board<size>::State& rhv) {
    return  state_ == rhv.state_;
};

template <int size>
bool Board<size>::State::CanMoveLeft() const {
    return zero_index_ % width_ != 0;
}

template <int size>
bool Board<size>::State::CanMoveUp() const {
    return zero_index_ > width_ - 1;
}

template <int size>
bool Board<size>::State::CanMoveDown() const {
    return zero_index_ < size - width_;
}

template <int size>
bool Board<size>::State::CanMoveRight() const {
    return  (zero_index_ + 1) % width_ != 0;
}

template <int size>
Board<size>::State::State(uint64_t state, size_t zero_index, size_t width, size_t turn_number)
: state_(state)
, zero_index_(zero_index)
, width_(width)
, number_of_turn(turn_number)
{}

template <int size>
class Board<size>::State Board<size>::State::MoveLeft() const {
        State moved_left(state_, zero_index_ - 1, width_, number_of_turn + 1);
        size_t digit = this->Get(zero_index_ - 1);
        moved_left.Set(zero_index_ - 1, 0);
        moved_left.Set(zero_index_, digit);
        return moved_left;
}

template <int size>
class Board<size>::State Board<size>::State::MoveUp() const {
        State moved_up(state_, zero_index_ - width_, width_, number_of_turn + 1);
        size_t digit = this->Get(zero_index_ - width_);
        moved_up.Set(zero_index_ - width_, 0);
        moved_up.Set(zero_index_, digit);
        return moved_up;
}

template <int size>
class Board<size>::State Board<size>::State::MoveRight() const {
        State moved_right(state_, zero_index_ + 1, width_, number_of_turn + 1);
        size_t digit = this->Get(zero_index_ + 1);
        moved_right.Set(zero_index_ + 1, 0);
        moved_right.Set(zero_index_, digit);
        return moved_right;
}

template <int size>
class Board<size>::State Board<size>::State::MoveDown() const {
        State moved_down(state_, zero_index_ + width_, width_, number_of_turn + 1);
        size_t digit = this->Get(zero_index_ + width_);
        moved_down.Set(zero_index_ + width_, 0);
        moved_down.Set(zero_index_, digit);
        return moved_down;
}

template <int size>
Board<size>::Board(const std::vector<size_t>& positions)
{
        size_t n = 1;
        while (n * n != size) {
            n += 1;
        }
        board_width_ = n;
        std::vector<size_t> target;
        for (int i = 1; i < size; ++i) {
            target.push_back(i);
        }
        target.push_back(0);
        target_ = State(target, n, 0);
        source_ = State(positions, n, 0);
        parents_[source_.GetState()] = {0, 0};
        have_solution_ = ExistSolution(positions);
}

template <int size>
Board<size>::State::State(const std::vector<size_t>& combinations, size_t width, size_t turn_number)
: width_(width)
, number_of_turn(turn_number)
{
    for (size_t i = 0; i < combinations.size(); ++i) {
        if (combinations[i] == 0) {
            zero_index_ = i;
        }
        state_ = state_ << 4;
        state_ += combinations[i];
    }
}

template <int size>
uint64_t Board<size>::State::GetState() const {
    return state_;
}

template <int size>
size_t Board<size>::State::Get(size_t index) const {
    uint64_t digit = state_ & masks_[masks_.size() - size + index];
    digit = digit >> 4 * (size - index - 1);
    return static_cast<size_t >(digit);
}

template <int size>
void Board<size>::State::Set(size_t index, size_t number) {
    uint64_t digit = static_cast<uint64_t >(number);
    digit = digit << 4 * (size - index - 1);
    state_ = state_ & anti_masks_[masks_.size() - size + index];
    state_ = state_ | digit;
}

template<int size>
const std::vector<uint64_t> Board<size>::State::masks_ = {17293822569102704640u, 1080863910568919040u,
                                                          67553994410557440u, 4222124650659840u, 263882790666240u,
                                                          16492674416640u, 1030792151040u, 64424509440u, 4026531840u,
                                                          251658240u, 15728640u, 983040u, 61440u, 3840u, 240u, 15u};
template<int size>
const std::vector<uint64_t> Board<size>::State::anti_masks_ = {1152921504606846975u, 17365880163140632575u,
                                                               18379190079298994175u, 18442521949058891775u,
                                                               18446480190918885375u, 18446727581035134975u,
                                                               18446743042917400575u, 18446744009285042175u,
                                                               18446744069683019775u, 18446744073457893375u,
                                                               18446744073693822975u, 18446744073708568575u,
                                                               18446744073709490175u, 18446744073709547775u,
                                                               18446744073709551375u, 18446744073709551600u};