Робот в арене: где он остановится?

В игре есть прямоугольная арена из клеток размером N×M. Робот начинает в клетке (r, c). Дальше игра проигрывает строку команд из букв U, D, L, R.

Робот пытается выполнить команды по очереди:

• U — на клетку выше (r уменьшается на 1),
• D — на клетку ниже (r увеличивается на 1),
• L — на клетку левее (c уменьшается на 1),
• R — на клетку правее (c увеличивается на 1).

Если команда уводит робота за границу арены, робот остаётся на месте и переходит к следующей команде.

Нужно узнать, в какой клетке робот окажется после всех команд.

Формат ввода

В первой строке записаны два целых числа N и M — размеры арены. Во второй строке записаны два целых числа r и c — стартовая позиция робота (строка и столбец). В третьей строке записана строка S из символов U, D, L, R.

Формат вывода

Выведите два числа — конечные r и c.

Ограничения

• 1 ≤ N, M ≤ 10^9
• 1 ≤ r ≤ N, 1 ≤ c ≤ M
• 1 ≤ |S| ≤ 2000

Пример

Ввод:

3 4
2 2
UURRDDL

Вывод:

3 3

Ключевое наблюдение: команда влияет только на текущую позицию робота, а поле огромным быть не мешает — нам не нужно хранить N×M клеток, достаточно держать две координаты (r, c). Поэтому решение — простая симуляция (прогон команд) с проверкой «влезли ли в границы».

Почему это работает: правила говорят, что если шаг выводит за арену, позиция не меняется. Значит, для каждой буквы мы можем вычислить «кандидат» (nr, nc) и либо принять его, либо отбросить.

План:

• Считай N, M, стартовые r, c и строку S.
• Для каждого символа ch из S:
• Заведи nr = r, nc = c.
• Измени nr/nc по направлению (U: nr-1, D: nr+1, L: nc-1, R: nc+1).
• Если 1 <= nr <= N и 1 <= nc <= M, присвой r = nr, c = nc, иначе оставь как было.
• Выведи r и c.

Мини-сниппет проверки: if 1 <= nr <= N and 1 <= nc <= M: r, c = nr, nc

Сложность: O(|S|) по времени (до 2000 шагов) и O(1) по памяти.

Частая ошибка: перепутать строки и столбцы (U/D меняют r, L/R меняют c) или забыть, что индексация 1..N и 1..M, а не 0..N-1.