import random

rng = random.Random()
rng.seed(42)

class _2048:
    dir = {
        'UP': (-1, 0),
        'DOWN': (1, 0),
        'LEFT': (0, -1),
        'RIGHT': (0, 1)
    }

    def __init__(self, board: list[list[int]] | None = None):
        self.board = board or [[0] * 4 for _ in range(4)]

    def clone(self):
        return _2048([row[:] for row in self.board])

    def is_game_over(self) -> bool:
        for direction in self.dir:
            if self.can_move(direction):
                return False
        return True

    def can_move(self, direction: str) -> bool:
        dx, dy = self.dir[direction]
        for i in range(4):
            for j in range(4):
                x, y = i, j
                if self.board[x][y] == 0:
                    continue
                if 0 <= x + dx < 4 and 0 <= y + dy < 4:
                    if self.board[x + dx][y + dy] == 0 or self.board[x + dx][y + dy] == self.board[x][y]:
                        return True
        return False

    def move(self, direction: str, add_tile: bool = True) -> bool:
        if not self.can_move(direction):
            return False

        dx, dy = self.dir[direction]
        merged = [[False] * 4 for _ in range(4)]

        if direction in ['UP', 'LEFT']:
            for i in range(4):
                for j in range(4):
                    self._slide_tile(i, j, dx, dy, merged)
        else:
            for i in range(3, -1, -1):
                for j in range(3, -1, -1):
                    self._slide_tile(i, j, dx, dy, merged)

        if add_tile:
            self.add_random_tile()
        return True

    def _slide_tile(self, i: int, j: int, dx: int, dy: int, merged: list[list[bool]]):
        x, y = i, j
        while 0 <= x + dx < 4 and 0 <= y + dy < 4:
            if self.board[x][y] == 0:
                break
            if self.board[x + dx][y + dy] == 0:
                self.board[x + dx][y + dy] = self.board[x][y]
                self.board[x][y] = 0
                x += dx
                y += dy
            elif self.board[x + dx][y + dy] == self.board[x][y] and not merged[x + dx][y + dy]:
                self.board[x + dx][y + dy] *= 2
                self.board[x][y] = 0
                merged[x + dx][y + dy] = True
                break
            else:
                break

    def add_tile(self, i: int, j: int, v: int):
        self.board[i][j] = v

    def add_random_tile(self):
        empty_cells = [(i, j) for i in range(4) for j in range(4) if self.board[i][j] == 0]
        if not empty_cells:
            return False, (-1, -1, 0)
        i, j = rng.choice(empty_cells)
        self.add_tile(i, j, 2 if rng.random() < 0.9 else 4)
        return True, (i, j, self.board[i][j])

import sys
class Interactive:

    def __init__(self):
        self._stdin = sys.stdin
        self._stdout = sys.stdout
        # Redirect print() to stderr so it doesn't go to user program
        sys.stdout = sys.stderr

    @property
    def input(self):
        return self.input_path.read_text()

    def readline(self):
        """Read one line from user program."""
        line = self._stdin.readline()
        if not line:
            self.wrong_answer("Unexpected EOF from solution")
        return line.rstrip("\n")

    def writeline(self, line):
        """Write one line to user program."""
        self._stdout.write(str(line) + "\n")
        self._stdout.flush()

    def writelines(self, lines):
        """Write multiple lines to user program."""
        for line in lines:
            self.writeline(line)

    def accept(self, message=""):
        if message:
            print(message)  # goes to stderr
        sys.exit(0)

    def wrong_answer(self, message=""):
        if message:
            print(message)
        sys.exit(1)

    def fail(self, message=""):
        if message:
            print(message)
        sys.exit(3)

interactor = Interactive()

game = _2048()

def num(i, j): return (i * 4 + j) + 1

_, (i, j, b) = game.add_random_tile()
a = num(i, j)
_, (i, j, d) = game.add_random_tile()
c = num(i, j)
interactor.writeline(f"{a} {b} {c} {d}")

while True:

    print("==== Board ===")
    for row in game.board:
        print(" ".join(map(str, row)))
    print("===============")
    print("Type UP, DOWN, LEFT, or RIGHT to move: ", end="")
    sys.stderr.flush()

    m = interactor.readline().strip()
    if m == "UP":
        if not game.move("UP", add_tile=False):
            interactor.writeline("-1")
            interactor.wrong_answer("Invalid Move")
    elif m == "DOWN":
        if not game.move("DOWN", add_tile=False):
            interactor.writeline("-1")
            interactor.wrong_answer("Invalid Move")
    elif m == "LEFT":
        if not game.move("LEFT", add_tile=False):
            interactor.writeline("-1")
            interactor.wrong_answer("Invalid Move")
    elif m == "RIGHT":
        if not game.move("RIGHT", add_tile=False):
            interactor.writeline("-1")
            interactor.wrong_answer("Invalid Move")
    else:
        interactor.writeline("-1")
        interactor.wrong_answer("Invalid Move")

    mx = max(max(row) for row in game.board)
    if mx >= 2048:
        interactor.writeline("-1")
        interactor.accept("You Win!")

    over = game.is_game_over()
    if over:
        interactor.writeline("-1")
        interactor.wrong_answer("Game Over")
    else:
        _, (i, j, v) = game.add_random_tile()
        if i == -1:
            interactor.writeline("-1")
            interactor.wrong_answer("No Empty Cell")
        else:
            interactor.writeline(f"{num(i, j)} {v}")