#include <assert.h>
#include <fstream>
#include <queue>
#include <set>
#include <sstream>
#include <string>

using namespace std;

//const vector<int> goal = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 }; // Положение фишек, до которого нужно дойти
const unsigned long long goal = 1147797409030816545; // Положение фишек, до которого нужно дойти
const vector<int> x = { 4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3 }; // Положение, в котором должны оказаться фишки
const vector<int> y = { 4,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4 };
const vector<int> maskX = { 1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4 };
const vector<int> maskY = { 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4 };
const unsigned long long Masks[] = {
	0x000000000000000F,
	0x00000000000000F0,
	0x0000000000000F00,
	0x000000000000F000,
	0x00000000000F0000,
	0x0000000000F00000,
	0x000000000F000000,
	0x00000000F0000000,
	0x0000000F00000000,
	0x000000F000000000,
	0x00000F0000000000,
	0x0000F00000000000,
	0x000F000000000000,
	0x00F0000000000000,
	0x0F00000000000000,
	0xF000000000000000,
};
const unsigned long long AntiMasks[] = {
	0xFFFFFFFFFFFFFFF0,
	0xFFFFFFFFFFFFFF0F,
	0xFFFFFFFFFFFFF0FF,
	0xFFFFFFFFFFFF0FFF,
	0xFFFFFFFFFFF0FFFF,
	0xFFFFFFFFFF0FFFFF,
	0xFFFFFFFFF0FFFFFF,
	0xFFFFFFFF0FFFFFFF,
	0xFFFFFFF0FFFFFFFF,
	0xFFFFFF0FFFFFFFFF,
	0xFFFFF0FFFFFFFFFF,
	0xFFFF0FFFFFFFFFFF,
	0xFFF0FFFFFFFFFFFF,
	0xFF0FFFFFFFFFFFFF,
	0xF0FFFFFFFFFFFFFF,
	0x0FFFFFFFFFFFFFFF
};
const int maxQueueSize = 65;
const int truncateKoeff = 3;
const bool truncateQ = true;

struct CLastPos {
	char pos; // Шаг, которым получена данная конфигурация
	CLastPos* pointer;
	CLastPos( char pos, CLastPos* pointer ) : pos( pos ), pointer( pointer ) {}
};

class CPosition {
public:
	explicit CPosition( const std::string& source );

	// Передвижение пустышки вверх, вниз, влево, вправо
	CPosition inline Up() const;
	CPosition inline Down() const;
	CPosition inline Left() const;
	CPosition inline Right() const;

	vector<int> inline GetVector() const;
	int GetNullPos() const { return nullPos; }
	unsigned long long GetData() const { return data; }
	int GetSteps() const { return steps; }
	CLastPos* GetLastDir() const { return lastPosition; }
	int prediction;

private:
	int nullPos;
	unsigned long long data; // 16 ячеек по 4 бита каждая.
	int steps; // Число ходов, которое сделано для достижения данного состояния
	CLastPos* lastPosition;

	void inline setAt( int place, unsigned char value );
	unsigned char inline getAt( int place ) const;
};

CPosition::CPosition( const string& source ) :
	data( 0 ),
	nullPos( 0 ),
	steps( 0 ),
	prediction( 0 ),
	lastPosition( NULL )
{
	//istringstream stringStream( source );
	for (char i = 0; i < 16; ++i) {
		unsigned short value = source[i];
		//stringStream >> value;
		setAt( i, static_cast<unsigned char>(value) );
		if (value == 0) {
			nullPos = i;
		}
	}
}

// Установка значения в некоторую позицию.
void inline CPosition::setAt( int place, unsigned char value )
{
	data = (data & AntiMasks[place]) | (static_cast<long long>(value) << (place << 2));
}

// Получение того, что лежит в некоторой позиции.
unsigned char inline CPosition::getAt( int place ) const
{
	return static_cast<unsigned char>((data & Masks[place]) >> (place << 2));
}

CPosition inline CPosition::Up() const
{
	assert( nullPos >= 4 );

	CPosition result( *this );

	// Ставим пустышку выше.
	result.setAt( nullPos - 4, 0 );
	// Ставим то, что было выше, на то место, где была пустышка.
	result.setAt( nullPos, getAt( nullPos - 4 ) );
	result.nullPos -= 4;
	result.lastPosition = new CLastPos( 'D', this->lastPosition );
	result.steps++;
	return result;
}

CPosition inline CPosition::Down() const
{
	assert( nullPos <= 11 );

	CPosition result( *this );

	result.setAt( nullPos + 4, 0 );
	result.setAt( nullPos, getAt( nullPos + 4 ) );
	result.nullPos += 4;
	result.lastPosition = new CLastPos( 'U', this->lastPosition );
	result.steps++;
	return result;
}

CPosition inline CPosition::Left() const
{
	assert( nullPos != 0 && nullPos != 4 && nullPos != 8 && nullPos != 12 );

	CPosition result( *this );

	result.setAt( nullPos - 1, 0 );
	result.setAt( nullPos, getAt( nullPos - 1 ) );
	result.nullPos -= 1;
	result.lastPosition = new CLastPos( 'R', this->lastPosition );
	result.steps++;
	return result;
}

CPosition inline CPosition::Right() const
{
	assert( nullPos != 3 && nullPos != 7 && nullPos != 11 && nullPos != 15 );

	CPosition result( *this );

	result.setAt( nullPos + 1, 0 );
	result.setAt( nullPos, getAt( nullPos + 1 ) );
	result.nullPos += 1;
	result.lastPosition = new CLastPos( 'L', this->lastPosition );
	result.steps++;
	return result;
}

vector<int> inline CPosition::GetVector() const
{
	vector<int> res( 16, 0 );
	for (int i = 0; i < 16; i++) {
		res[i] = getAt( i );
	}
	return res;
}

class Compare {
public:
	bool operator()( const CPosition& left, const CPosition& right )
	{
		return left.prediction > right.prediction;
	}
};

bool check_solvability( const CPosition& board )
{
	vector<int> numbers = board.GetVector();
	bool chetn = true;
	for (size_t i = 0; i < 16; ++i) {
		if (numbers[i] == 0) continue;
		for (size_t j = i; j < 16; ++j) {
			if (numbers[j] == 0) continue;
			if (numbers[i] < numbers[j]) {
				chetn = !chetn;
			}
		}
	}
	int nullPos = board.GetNullPos();
	bool line = false; // Четность строки, где стоит пустышка. Нумерация с 1
	if ((nullPos >= 4 && nullPos <= 7) || (nullPos >= 12 && nullPos <= 15)) {
		line = true;
	}
	return ((!chetn&&line) || (chetn && !line)); // xor
}

int inline heuristic( vector<int>& boardVector )
{
	// Manhattan distance
	int res = 0;
	for (size_t i = 0; i < 16; i++) {
		if (boardVector[i] != 0) {
			res += abs( x[boardVector[i]] - maskX[i] );
			res += abs( y[boardVector[i]] - maskY[i] );
		}
	}

	// Linear conflict
	// Перебираем строки
	for (int i = 0; i < 4; ++i) {
		// Перебираем первые 3 элемента в строке
		for (int j = 0; j < 3; ++j) {
			// Если элемент в решенном состоянии должен быть в этой строке
			int tile1 = boardVector[4 * i + j];
        if(tile1==0) continue;
			if (tile1 >= 4*i + 1 && tile1 <= 4*i + 4) {
				// Перебираем элементы правее него
				for (int k = j + 1; k < 4; ++k) {
					int tile2 = boardVector[4 * i + k];if(tile2==0) continue;
					if (tile2 >= 4 * i + 1 && tile2 <= 4 * i + 4 && tile2 < tile1) {
						res += 2;
					}
				}
			}
		}
	}
	// Перебираем столбцы
	for (int i = 0; i < 4; ++i) {
		// Перебираем первые 3 элемента в столбце
		for (int j = 0; j < 3; ++j) {
			// Если элемент в решенном состоянии должен быть в этом столбце
			int tile1 = boardVector[4 * j + i];if(tile1==0) continue;
			if ((tile1 - 1) % 4 == i) {
				// Перебираем элементы ниже него
				for (int k = j + 1; k < 4; ++k) {
					int tile2 = boardVector[4 * k + i];if(tile2==0) continue;
					if ((tile2 - 1) % 4 == i && tile2 < tile1) {
						res += 2;
					}
				}
			}
		}
	}


	//int ret = 0;
	//// строка
	//int row[] = { 3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3 };
	//// столбец
	//int column[] = { 3, 0 ,1 ,2, 3, 0 ,1 ,2, 3, 0 ,1 ,2, 3, 0 ,1 ,2 };

	//// строки
	//for (int i = 0; i < 4; i++)
	//	for (int j = 0; j < 4; j++) {
	//		int currNum = posTable[i][j];
	//		for (int k = j + 1; k < 4; k++) {
	//			if (row[posTable[i][k]] == row[posTable[i][j]] && column[posTable[i][k]] < column[posTable[i][j]])
	//				ret += 2;
	//		}
	//	}
	//// столбца
	//for (int j = 0; j < 4; j++)
	//	for (int i = 0; i < 4; i++) {
	//		int currNum = posTable[i][j];
	//		for (int k = i + 1; k < 4; k++) {
	//			if (column[posTable[k][j]] == column[posTable[i][j]] && row[posTable[k][j]] < row[posTable[i][j]])
	//				ret += 2;
	//		}
	//	}
	//return ret;

	return res;
}

template <typename TQueue>
void inline finderStep( set<unsigned long long>& prev_states, TQueue& q, CPosition& board )
{
	// Пытаемся сделать шаг в одном из направлений, запоминаем путь
	char last_dir = 0;
	if (board.GetLastDir() != NULL)
		last_dir = board.GetLastDir()->pos;
	int nullPos = board.GetNullPos();

	// Up
	if (last_dir != 'U' && nullPos >= 4) {
		CPosition tmpBoard = board.Up();
		if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
			vector<int> qwerty = tmpBoard.GetVector();
			tmpBoard.prediction = heuristic( qwerty );
			q.push( tmpBoard );
			prev_states.insert( tmpBoard.GetData() );
		}
	}
	// Down
	if (last_dir != 'D' && nullPos <= 11) {
		CPosition tmpBoard = board.Down();
		if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
			vector<int> qwerty = tmpBoard.GetVector();
			tmpBoard.prediction = heuristic( qwerty );
			q.push( tmpBoard );
			prev_states.insert( tmpBoard.GetData() );
		}
	}
	// Left
	if (last_dir != 'L' && nullPos != 0 && nullPos != 4 && nullPos != 8 && nullPos != 12) {
		CPosition tmpBoard = board.Left();
		if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
			vector<int> qwerty = tmpBoard.GetVector();
			tmpBoard.prediction = heuristic( qwerty );
			q.push( tmpBoard );
			prev_states.insert( tmpBoard.GetData() );
		}
	}
	// Right
	if (last_dir != 'R' && nullPos != 3 && nullPos != 7 && nullPos != 11 && nullPos != 15) {
		CPosition tmpBoard = board.Right();
		if (prev_states.find( tmpBoard.GetData() ) == prev_states.end() || tmpBoard.GetSteps() + 1 < board.GetSteps()) {
			vector<int> qwerty = tmpBoard.GetVector();
			tmpBoard.prediction = heuristic( qwerty );
			q.push( tmpBoard );
			prev_states.insert( tmpBoard.GetData() );
		}
	}
}

template <typename TQueue>
void inline truncateQueue( TQueue& q )
{
	priority_queue<CPosition, vector<CPosition>, Compare> tempQ;
	int newSize = maxQueueSize / truncateKoeff;
	for (size_t i = 0; i < newSize; i++) {
		CPosition tempElem = q.top();
		q.pop();
		tempQ.push( tempElem );
	}
	q = tempQ;
}

void findSolution( CPosition& givenBoard, int& steps, string& solution )
{
	set<unsigned long long> prev_states;
	priority_queue<CPosition, vector<CPosition>, Compare> q;
	prev_states.insert( givenBoard.GetData() );
	q.push( givenBoard );
	while (!q.empty()) {
		CPosition board = q.top();
		q.pop();

		if (board.GetData() == goal) {
			steps = board.GetSteps();
			string invertedSolution = "";
			CLastPos* lastDir = board.GetLastDir();
			for (size_t i = 0; i < steps; i++) {
				invertedSolution += lastDir->pos;
				lastDir = lastDir->pointer;
			}
			for (size_t i = 0; i < steps; i++) {
				solution += invertedSolution[steps - i - 1];
			}
			return;
		}

		// Пытаемся сделать шаг в одном из направлений, запоминаем путь
		finderStep( prev_states, q, board );

		// Для ускорения удаляем элементы с наибольшей удаленностью
		if ( truncateQ && q.size() > maxQueueSize) {
			truncateQueue( q );
		}
	}
}

int main()
{
	ifstream fin( "input.txt" );
	string state = "";
	for (size_t i = 1; i <= 16; i++) {
		int number = 0;
		fin >> number;
		state += (char) number;
	}
	fin.close();

	CPosition board( state );

	vector<int> t = board.GetVector();

	int steps = 1000; // Минимальное количество ходов в решении
	string solution = ""; // Последовательность ходов

	if (!check_solvability( board )) {
		ofstream fout( "output.txt" );
		fout << -1;
		fout.close();
		return 0;
	}

	findSolution( board, steps, solution );

	ofstream fout( "output.txt" );
	fout << steps;
	fout << '\n';
	fout << solution.c_str();
	fout.close();
	return 0;
}