//
//  main.cpp
//  Пятнашки
//
//  Created by Матвей on 12.03.2018.
//  Copyright © 2018 Матвей. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cassert>

using namespace std;

class Graph{
public:
    struct Vertex{
        vector<int> Condition;
        int depth;
        int heuristic;
        Vertex* parent = nullptr;
        char WhichMove;
    };

    Graph(vector<int>& Start);
    void RestoreTheWay();
    bool Compare( const Graph::Vertex& first, const Graph::Vertex& second );
    void GetNextVertex(Vertex Start, vector<Vertex>& NextVert );
    void PrintAnswer();
    bool IsFinalCondition(Vertex v);
    int CountTheHeuristic( Vertex v );
    Vertex AStar();

private:
    Vertex Start;
    string Way;
    int NumOfMoves;
};

bool operator<( const Graph::Vertex& first, const Graph::Vertex& second )
{
    return first.depth < second.depth;
}

void Graph::PrintAnswer(){
    cout << Way << endl << NumOfMoves;
}

void Graph::RestoreTheWay(){
    string ReverseWay;
    NumOfMoves = 0;
    Vertex Final = AStar();
    Vertex* tmp = &Final;
    while( tmp->parent != nullptr ) {
        ReverseWay += Final.WhichMove;
        NumOfMoves += 1;
        tmp = tmp->parent;
    }
    int j = 0;
    for( int i = (int)ReverseWay.length(); i >=0; i-- ) {
        Way[j] += ReverseWay[i];
        j++;
    }

}


Graph::Vertex Graph::AStar()
{
    priority_queue<Vertex, vector<Vertex>, less<Vertex>> q;
    map<Vertex, int> used;
    used.insert(make_pair(Start, 0));
    q.push(Start);
    //дописать хрен знает что

    while( !q.empty() ) {
        Vertex tmp = q.top();
        q.pop();

        if( IsFinalCondition(tmp) ) return tmp;

        vector<Vertex> NextVert;
        GetNextVertex(tmp, NextVert);

        for( auto v : NextVert ) {
            int new_cost = used[tmp] + 1;
            if( used.count(v) == 0 || new_cost < used[v] ) {
                used.insert(make_pair(v, new_cost));
                v.depth = new_cost + v.heuristic;
                q.push(v);
            }
        }

    }

    assert(1 == 2);
    return Start;
}

Graph::Graph( vector<int>& StartCondition )
{
    //    Vertex Start;
    for(auto i : StartCondition){
        Start.Condition.push_back(i);
    }
    Start.depth = 0;
    Start.heuristic = CountTheHeuristic(Start);
    Start.parent = nullptr;
    Start.WhichMove = '0';
}

int Graph::CountTheHeuristic(Vertex v)
{
    int Heuristic = 0;
    for( int i = 0; i < v.Condition.size(); i++ ) {
        int elem = v.Condition[i];
        //
        Heuristic += (abs(elem-1-i)/4)+(abs(elem-1-i)%4);
    }
    return Heuristic;
}

bool Graph::IsFinalCondition(Vertex v)
{
    for( int i = 1; i <= v.Condition.size(); i++ ) {
        if( i != v.Condition.size() ) {
            if( i != v.Condition[i-1] ) return false;
        } else {
            if( v.Condition[i-1] != 0 ) return false;
        }
    }
    return true;
}

void Graph::GetNextVertex(Vertex Start, vector<Vertex>& NextVert)
{
    // тут выделяю локальные переменные под tmp и беру указатель на них
    // видимо, после выхода, память, которая была заведена под них освобождается
    // и все идет очень фигово дальше
    int SpacePosition = 0;
    for( int i = 0; i < (int)Start.Condition.size(); i++ ) {
        if( Start.Condition[i] == 0 ){
            SpacePosition = i;
            break;
        }
    }

    if( SpacePosition < Start.Condition.size() - 1 ) {
        Vertex tmp;
        tmp.Condition.resize(Start.Condition.size());
        for( int i = 0; i < Start.Condition.size(); i++ ) {
            tmp.Condition[i] = Start.Condition[i];
        }
        swap(tmp.Condition[SpacePosition],tmp.Condition[SpacePosition+1]);
        tmp.parent = &Start;
        int heuristic = CountTheHeuristic(tmp);
        tmp.heuristic = heuristic;
        tmp.WhichMove = 'R';
        NextVert.push_back(tmp);
    }

    if( SpacePosition > 0 ){
        Vertex tmp;
        tmp.Condition.resize(Start.Condition.size());
        for( int i = 0; i < Start.Condition.size(); i++ ) {
            tmp.Condition[i] = Start.Condition[i];
        }
        swap(tmp.Condition[SpacePosition],tmp.Condition[SpacePosition-1]);
        tmp.parent = &Start;
        int heuristic = CountTheHeuristic(tmp);
        tmp.heuristic = heuristic;
        tmp.WhichMove = 'L';
        NextVert.push_back(tmp);
    }

    if( SpacePosition >= 4 ){
        Vertex tmp;
        tmp.Condition.resize(Start.Condition.size());
        for( int i = 0; i < Start.Condition.size(); i++ ) {
            tmp.Condition[i] = Start.Condition[i];
        }
        swap(tmp.Condition[SpacePosition],tmp.Condition[SpacePosition-4]);
        tmp.parent = &Start;
        int heuristic = CountTheHeuristic(tmp);
        tmp.heuristic = heuristic;
        tmp.WhichMove = 'U';
        NextVert.push_back(tmp);
    }

    if( SpacePosition <= Start.Condition.size() - 5 ){
        Vertex tmp;
        tmp.Condition.resize(Start.Condition.size());
        for( int i = 0; i < Start.Condition.size(); i++ ) {
            tmp.Condition[i] = Start.Condition[i];
        }
        swap(tmp.Condition[SpacePosition],tmp.Condition[SpacePosition+4]);
        tmp.parent = &Start;
        int heuristic = CountTheHeuristic(tmp);
        tmp.heuristic = heuristic;
        tmp.WhichMove = 'D';
        NextVert.push_back(tmp);
    }

}

int main() {
    vector<int> g;
    for( int i = 0; i < 16; i++ ) {
        int tmp = 0;
        cin >> tmp;
        g.push_back(tmp);
    }
    Graph graph(g);
    //    graph.AStar();
    graph.RestoreTheWay();
    graph.PrintAnswer();
    return 0;
}