#include <bits/stdc++.h>
// #include "solution.h"
using namespace std;
 
#define rep(i, j) for (int i = 0; i < 4; i++)\
	for (int j = 0; j < 4; j++)
 
typedef array<array<int, 4>, 4> board;
 
board flip(board a, bool z = 1) {
	board b;
	rep(i, j) {
		if (z) b[i][j] = a[j][i];
		else b[i][j] = a[3 - j][3 - i];
	}
	return b;
}
 
 
board dir(board a, char c) {
	if (c == 'U') return a;
	if (c == 'L') return flip(a);
	if (c == 'R') return flip(a, 0);
	return flip(flip(a, 0));
}
 
board move(board a, char c) {
	a = dir(a, c);
	rep(j, i) {
		if (a[i][j] == 0) continue;
		for (int k = i + 1; k < 4; k++) {
			if (a[k][j] == 0) continue;
			if (a[i][j] == a[k][j]) {
				a[i][j] *= -2;
				a[k][j] = 0;
			}
			break;
		}
	}
	rep(i, j) if (a[i][j] < 0) a[i][j] = -a[i][j];
	rep(j, i) {
		if (a[i][j] > 0) continue;
		for (int k = i + 1; k < 4; k++) {
			if (a[k][j] > 0) {
				a[i][j] = a[k][j];
				a[k][j] = 0;
				break;
			}
		}
	}
	a = dir(a, c);
	return a;
}
 
board put(board a) {
	vector<pair<int, int>> zeros;
	rep(i, j) if (a[i][j] == 0) zeros.push_back({i, j});
	int p = rand() % 100;
	int k = rand() % zeros.size();
	int i = zeros[k].first;
	int j = zeros[k].second;
	int val = (p < 10) ? 4 : 2;
	a[i][j] = val;
	return a;
}
 
// BEGIN
// Энд функц заралж ашиглаж болно
 
board flip1(board a, bool z = 1) {
	board b;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (z) 
                b[i][j] = a[j][i];
			else 
                b[i][j] = a[3 - j][3 - i];
		}
	}
	return b;
}
 
board dir1(board a, char c) {
	if (c == 'U') 
        return a;
	if (c == 'L') 
        return flip1(a);
	if (c == 'R') 
        return flip1(a, 0);
	return flip1(flip1(a, 0));
}
 
board move1(board a, char c) {
    a = dir1(a, c);
    for (int j = 0; j < 4; j++) {
        for (int i = 0; i < 4; i++) {
            if (a[i][j] == 0) continue;
            for (int k = i + 1; k < 4; k++) {
                if (a[k][j] == 0) continue;
                if (a[i][j] == a[k][j]) {
                    a[i][j] *= -2;
                    a[k][j] = 0;
                }
                break;
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (a[i][j] < 0) a[i][j] = -a[i][j];
        }
    }
    for (int j = 0; j < 4; j++) {
        for (int i = 0; i < 4; i++) {
            if (a[i][j] > 0) continue;
            for (int k = i + 1; k < 4; k++) {
                if (a[k][j] > 0) {
                    a[i][j] = a[k][j];
                    a[k][j] = 0;
                    break;
                }
            }
        }
    }
    a = dir1(a, c);
    return a;
}
 
bool over(const board& a, char move) {
    board b = move1(a, move);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (b[i][j] == 0) {
                return false;
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if ((i < 3 && b[i][j] == b[i + 1][j]) || (j < 3 && b[i][j] == b[i][j + 1])) {
                return false;
            }
        }
    }
    return true;
}
 
int find_sum(board a){
    int s=0;
    for (int i = 0; i < 4; i++){
        for (int j =0; j < 4; j++){
            if (a[i][j]==0){
                s++;
            }
        }
    }
    return s;
}
 
int evaluate(board a) {
    int score = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            score += a[i][j];
    return score;
}
 
char play(board a) {
    char moves[] = {'U', 'D', 'L', 'R'};
    int maxScore = INT_MIN;
    char bestMove = 'U';
 
    for (char move : moves) {
        board b = move1(a, move);
        if (b == a) continue; 
        int score = evaluate(b);
        if (score > maxScore) {
            maxScore = score;
            bestMove = move;
        }
    }
    return bestMove;
}
 
 
// Энд бичсэн хэсгээ л сервэрт илгээнэ
// END
 
int main(int argc, char **argv) {
	string token;
	if (argc == 2) token = argv[1];
	srand(247);
	srand(time(0));
	board a; rep(i, j) a[i][j] = 0;
 
	int itr = 0;
	clock_t begin = clock();
	while (true) {
		char c = play(a);
		rep(i, j) cout << a[i][j] << " \n"[j == 3];
		cout << c << "\n";
		if (c != 'U' && c != 'R' && c != 'D' && c != 'L') break;
		board b = move(a, c);
		if (itr > 0 && b == a) break;
		a = put(b);
		double timer = double(clock() - begin) / CLOCKS_PER_SEC;
		if (timer > 10) break;
		itr++;
	}
	int score = 0;
	rep(i, j) score += a[i][j];
	cout << "Score: " << score << endl;
	cout << "Last state:\n";
	rep(i, j) cout << a[i][j] << " \n"[j == 3];
	double timer = double(clock() - begin) / CLOCKS_PER_SEC;
	cout << "Time: " << (int)timer <<"sec\n";
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Ci8vICNpbmNsdWRlICJzb2x1dGlvbi5oIgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSByZXAoaSwgaikgZm9yIChpbnQgaSA9IDA7IGkgPCA0OyBpKyspXAoJZm9yIChpbnQgaiA9IDA7IGogPCA0OyBqKyspCgp0eXBlZGVmIGFycmF5PGFycmF5PGludCwgND4sIDQ+IGJvYXJkOwoKYm9hcmQgZmxpcChib2FyZCBhLCBib29sIHogPSAxKSB7Cglib2FyZCBiOwoJcmVwKGksIGopIHsKCQlpZiAoeikgYltpXVtqXSA9IGFbal1baV07CgkJZWxzZSBiW2ldW2pdID0gYVszIC0gal1bMyAtIGldOwoJfQoJcmV0dXJuIGI7Cn0KCgpib2FyZCBkaXIoYm9hcmQgYSwgY2hhciBjKSB7CglpZiAoYyA9PSAnVScpIHJldHVybiBhOwoJaWYgKGMgPT0gJ0wnKSByZXR1cm4gZmxpcChhKTsKCWlmIChjID09ICdSJykgcmV0dXJuIGZsaXAoYSwgMCk7CglyZXR1cm4gZmxpcChmbGlwKGEsIDApKTsKfQoKYm9hcmQgbW92ZShib2FyZCBhLCBjaGFyIGMpIHsKCWEgPSBkaXIoYSwgYyk7CglyZXAoaiwgaSkgewoJCWlmIChhW2ldW2pdID09IDApIGNvbnRpbnVlOwoJCWZvciAoaW50IGsgPSBpICsgMTsgayA8IDQ7IGsrKykgewoJCQlpZiAoYVtrXVtqXSA9PSAwKSBjb250aW51ZTsKCQkJaWYgKGFbaV1bal0gPT0gYVtrXVtqXSkgewoJCQkJYVtpXVtqXSAqPSAtMjsKCQkJCWFba11bal0gPSAwOwoJCQl9CgkJCWJyZWFrOwoJCX0KCX0KCXJlcChpLCBqKSBpZiAoYVtpXVtqXSA8IDApIGFbaV1bal0gPSAtYVtpXVtqXTsKCXJlcChqLCBpKSB7CgkJaWYgKGFbaV1bal0gPiAwKSBjb250aW51ZTsKCQlmb3IgKGludCBrID0gaSArIDE7IGsgPCA0OyBrKyspIHsKCQkJaWYgKGFba11bal0gPiAwKSB7CgkJCQlhW2ldW2pdID0gYVtrXVtqXTsKCQkJCWFba11bal0gPSAwOwoJCQkJYnJlYWs7CgkJCX0KCQl9Cgl9CglhID0gZGlyKGEsIGMpOwoJcmV0dXJuIGE7Cn0KCmJvYXJkIHB1dChib2FyZCBhKSB7Cgl2ZWN0b3I8cGFpcjxpbnQsIGludD4+IHplcm9zOwoJcmVwKGksIGopIGlmIChhW2ldW2pdID09IDApIHplcm9zLnB1c2hfYmFjayh7aSwgan0pOwoJaW50IHAgPSByYW5kKCkgJSAxMDA7CglpbnQgayA9IHJhbmQoKSAlIHplcm9zLnNpemUoKTsKCWludCBpID0gemVyb3Nba10uZmlyc3Q7CglpbnQgaiA9IHplcm9zW2tdLnNlY29uZDsKCWludCB2YWwgPSAocCA8IDEwKSA/IDQgOiAyOwoJYVtpXVtqXSA9IHZhbDsKCXJldHVybiBhOwp9CgovLyBCRUdJTgovLyDQrdC90LQg0YTRg9C90LrRhiDQt9Cw0YDQsNC70LYg0LDRiNC40LPQu9Cw0LYg0LHQvtC70L3QvgoKYm9hcmQgZmxpcDEoYm9hcmQgYSwgYm9vbCB6ID0gMSkgewoJYm9hcmQgYjsKCWZvciAoaW50IGkgPSAwOyBpIDwgNDsgaSsrKSB7CgkJZm9yIChpbnQgaiA9IDA7IGogPCA0OyBqKyspIHsKCQkJaWYgKHopIAogICAgICAgICAgICAgICAgYltpXVtqXSA9IGFbal1baV07CgkJCWVsc2UgCiAgICAgICAgICAgICAgICBiW2ldW2pdID0gYVszIC0gal1bMyAtIGldOwoJCX0KCX0KCXJldHVybiBiOwp9Cgpib2FyZCBkaXIxKGJvYXJkIGEsIGNoYXIgYykgewoJaWYgKGMgPT0gJ1UnKSAKICAgICAgICByZXR1cm4gYTsKCWlmIChjID09ICdMJykgCiAgICAgICAgcmV0dXJuIGZsaXAxKGEpOwoJaWYgKGMgPT0gJ1InKSAKICAgICAgICByZXR1cm4gZmxpcDEoYSwgMCk7CglyZXR1cm4gZmxpcDEoZmxpcDEoYSwgMCkpOwp9Cgpib2FyZCBtb3ZlMShib2FyZCBhLCBjaGFyIGMpIHsKICAgIGEgPSBkaXIxKGEsIGMpOwogICAgZm9yIChpbnQgaiA9IDA7IGogPCA0OyBqKyspIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDQ7IGkrKykgewogICAgICAgICAgICBpZiAoYVtpXVtqXSA9PSAwKSBjb250aW51ZTsKICAgICAgICAgICAgZm9yIChpbnQgayA9IGkgKyAxOyBrIDwgNDsgaysrKSB7CiAgICAgICAgICAgICAgICBpZiAoYVtrXVtqXSA9PSAwKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIGlmIChhW2ldW2pdID09IGFba11bal0pIHsKICAgICAgICAgICAgICAgICAgICBhW2ldW2pdICo9IC0yOwogICAgICAgICAgICAgICAgICAgIGFba11bal0gPSAwOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDQ7IGkrKykgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgNDsgaisrKSB7CiAgICAgICAgICAgIGlmIChhW2ldW2pdIDwgMCkgYVtpXVtqXSA9IC1hW2ldW2pdOwogICAgICAgIH0KICAgIH0KICAgIGZvciAoaW50IGogPSAwOyBqIDwgNDsgaisrKSB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCA0OyBpKyspIHsKICAgICAgICAgICAgaWYgKGFbaV1bal0gPiAwKSBjb250aW51ZTsKICAgICAgICAgICAgZm9yIChpbnQgayA9IGkgKyAxOyBrIDwgNDsgaysrKSB7CiAgICAgICAgICAgICAgICBpZiAoYVtrXVtqXSA+IDApIHsKICAgICAgICAgICAgICAgICAgICBhW2ldW2pdID0gYVtrXVtqXTsKICAgICAgICAgICAgICAgICAgICBhW2tdW2pdID0gMDsKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGEgPSBkaXIxKGEsIGMpOwogICAgcmV0dXJuIGE7Cn0KCmJvb2wgb3Zlcihjb25zdCBib2FyZCYgYSwgY2hhciBtb3ZlKSB7CiAgICBib2FyZCBiID0gbW92ZTEoYSwgbW92ZSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDQ7IGkrKykgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgNDsgaisrKSB7CiAgICAgICAgICAgIGlmIChiW2ldW2pdID09IDApIHsKICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgNDsgaSsrKSB7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCA0OyBqKyspIHsKICAgICAgICAgICAgaWYgKChpIDwgMyAmJiBiW2ldW2pdID09IGJbaSArIDFdW2pdKSB8fCAoaiA8IDMgJiYgYltpXVtqXSA9PSBiW2ldW2ogKyAxXSkpIHsKICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiB0cnVlOwp9CgppbnQgZmluZF9zdW0oYm9hcmQgYSl7CiAgICBpbnQgcz0wOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCA0OyBpKyspewogICAgICAgIGZvciAoaW50IGogPTA7IGogPCA0OyBqKyspewogICAgICAgICAgICBpZiAoYVtpXVtqXT09MCl7CiAgICAgICAgICAgICAgICBzKys7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gczsKfQoKaW50IGV2YWx1YXRlKGJvYXJkIGEpIHsKICAgIGludCBzY29yZSA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDQ7IGkrKykKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IDQ7IGorKykKICAgICAgICAgICAgc2NvcmUgKz0gYVtpXVtqXTsKICAgIHJldHVybiBzY29yZTsKfQoKY2hhciBwbGF5KGJvYXJkIGEpIHsKICAgIGNoYXIgbW92ZXNbXSA9IHsnVScsICdEJywgJ0wnLCAnUid9OwogICAgaW50IG1heFNjb3JlID0gSU5UX01JTjsKICAgIGNoYXIgYmVzdE1vdmUgPSAnVSc7CgogICAgZm9yIChjaGFyIG1vdmUgOiBtb3ZlcykgewogICAgICAgIGJvYXJkIGIgPSBtb3ZlMShhLCBtb3ZlKTsKICAgICAgICBpZiAoYiA9PSBhKSBjb250aW51ZTsgCiAgICAgICAgaW50IHNjb3JlID0gZXZhbHVhdGUoYik7CiAgICAgICAgaWYgKHNjb3JlID4gbWF4U2NvcmUpIHsKICAgICAgICAgICAgbWF4U2NvcmUgPSBzY29yZTsKICAgICAgICAgICAgYmVzdE1vdmUgPSBtb3ZlOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBiZXN0TW92ZTsKfQoKCi8vINCt0L3QtCDQsdC40YfRgdGN0L0g0YXRjdGB0LPRjdGNINC7INGB0LXRgNCy0Y3RgNGCINC40LvQs9GN0Y3QvdGNCi8vIEVORAoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKiphcmd2KSB7CglzdHJpbmcgdG9rZW47CglpZiAoYXJnYyA9PSAyKSB0b2tlbiA9IGFyZ3ZbMV07CglzcmFuZCgyNDcpOwoJc3JhbmQodGltZSgwKSk7Cglib2FyZCBhOyByZXAoaSwgaikgYVtpXVtqXSA9IDA7CgoJaW50IGl0ciA9IDA7CgljbG9ja190IGJlZ2luID0gY2xvY2soKTsKCXdoaWxlICh0cnVlKSB7CgkJY2hhciBjID0gcGxheShhKTsKCQlyZXAoaSwgaikgY291dCA8PCBhW2ldW2pdIDw8ICIgXG4iW2ogPT0gM107CgkJY291dCA8PCBjIDw8ICJcbiI7CgkJaWYgKGMgIT0gJ1UnICYmIGMgIT0gJ1InICYmIGMgIT0gJ0QnICYmIGMgIT0gJ0wnKSBicmVhazsKCQlib2FyZCBiID0gbW92ZShhLCBjKTsKCQlpZiAoaXRyID4gMCAmJiBiID09IGEpIGJyZWFrOwoJCWEgPSBwdXQoYik7CgkJZG91YmxlIHRpbWVyID0gZG91YmxlKGNsb2NrKCkgLSBiZWdpbikgLyBDTE9DS1NfUEVSX1NFQzsKCQlpZiAodGltZXIgPiAxMCkgYnJlYWs7CgkJaXRyKys7Cgl9CglpbnQgc2NvcmUgPSAwOwoJcmVwKGksIGopIHNjb3JlICs9IGFbaV1bal07Cgljb3V0IDw8ICJTY29yZTogIiA8PCBzY29yZSA8PCBlbmRsOwoJY291dCA8PCAiTGFzdCBzdGF0ZTpcbiI7CglyZXAoaSwgaikgY291dCA8PCBhW2ldW2pdIDw8ICIgXG4iW2ogPT0gM107Cglkb3VibGUgdGltZXIgPSBkb3VibGUoY2xvY2soKSAtIGJlZ2luKSAvIENMT0NLU19QRVJfU0VDOwoJY291dCA8PCAiVGltZTogIiA8PCAoaW50KXRpbWVyIDw8InNlY1xuIjsKCXJldHVybiAwOwp9