Робот находится на клетчатой прямоугольной доске размера \(n \times m\) (\(n\) строк, \(m\) столбцов). Строки в доске пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы — от \(1\) до \(m\) слева направо.
Робот умеет передвигаться из текущей клетки в одну из четырех соседних с ней по стороне.
Известна последовательность выполняемых роботом команд \(s\). Каждая команда обозначается одним из символов 'L', 'R', 'D' или 'U', и задает движение влево, вправо, вниз или вверх, соответственно.
Начать свое движение робот может в любой клетке. Команды робот выполняет, начиная с самой первой, строго в том порядке, в котором они перечислены в \(s\). Если робот перемещается за границу доски, он падает и ломается. Команда, приводящая к поломке робота, не считается успешно выполненной.
Задача робота — выполнить как можно больше команд, не упав с доски. Например, на доске \(3 \times 3\), начав исполнять последовательность действий \(s=\)«RRDLUU» («вправо», «вправо», «вниз», «влево», «вверх», «вверх») из центральной клетки, робот выполнит одну команду, после чего следующей командой выйдет за границу доски. Если же робот начнет движение из клетки \((2, 1)\) (вторая строка, первый столбец), то все команды будут успешно выполнены, и робот остановится в клетке \((1, 2)\) (первая строка, второй столбец).
Робот начинает из клетки \((2, 1)\) (вторая строка, первый столбец). Двигается вправо, вправо, вниз, влево, вверх и вверх. В этом случае он заканчивает в клетке \((1, 2)\) (первая строка, второй столбец). Определите, с какой клетки роботу стоит начинать свое движение, чтобы выполнить как можно больше команд.
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите два целых числа \(r\) (\(1 \leq r \leq n\)) и \(c\) (\(1 \leq c \leq m\)), разделенные пробелом — координаты клетки (номер строки и номер столбца), из которой роботу следует начинать движение, чтобы выполнить как можно больше команд.
Если таких клеток несколько, выведите любую.