K. Перепутанные пульты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Красный и синий роботы находятся в разных целочисленных точках плоскости. У каждого робота есть пульт с записанной последовательностью из $$$n$$$ команд.

Каждая команда перемещает робота на одну клетку:

  • U увеличивает координату $$$y$$$ на $$$1$$$;
  • D уменьшает координату $$$y$$$ на $$$1$$$;
  • L уменьшает координату $$$x$$$ на $$$1$$$;
  • R увеличивает координату $$$x$$$ на $$$1$$$.

Изначально красный робот держит первый пульт, а синий - второй.

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

Во время движения по единичному отрезку обмена быть не может. В частности, если роботы одновременно прошли навстречу друг другу и поменялись местами, но после команды оказались в разных точках, это не считается встречей.

После обмена нумерация команд продолжается: в следующую секунду каждый робот выполняет команду номер $$$i+1$$$ со своего нового пульта.

Обратите внимание, при некоторых входных данных обмен пультами может происходить после каждого перемещения. Это не противоречит условию задачи.

Определите конечные позиции красного и синего роботов после выполнения всех $$$n$$$ команд.

Входные данные

В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$).

Во второй строке даны четыре целых числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ — начальные координаты красного и синего роботов соответственно. Каждая координата находится в диапазоне от $$$-10^9$$$ до $$$10^9$$$. Начальные позиции роботов различны.

В третьей строке дана строка $$$s_1$$$ длины $$$n$$$ — команды первого пульта.

В четвёртой строке дана строка $$$s_2$$$ длины $$$n$$$ — команды второго пульта.

Обе строки состоят только из символов U, D, L и R.

Выходные данные

В первой строке выведите конечные координаты красного робота.

Во второй строке выведите конечные координаты синего робота.

Примеры
Входные данные
3
0 0 2 0
RRU
LLU
Выходные данные
0 1
2 1
Входные данные
3
0 0 2 0
RUU
LUR
Выходные данные
1 2
2 1
Входные данные
2
0 0 1 0
RU
LD
Выходные данные
1 1
0 -1
Примечание

В первом примере после первой секунды оба робота оказываются в точке $$$(1,0)$$$ и обмениваются пультами. Во вторую секунду красный робот выполняет команду L со второго пульта, а синий - команду R с первого. В третью секунду оба выполняют команду U.

Во втором примере роботы встречаются после первой и после второй секунды. Они дважды обмениваются пультами, поэтому третью команду каждый выполняет со своего исходного пульта.

В третьем примере после первой секунды роботы меняются позициями. Это не считается встречей, поэтому пульты остаются у прежних владельцев.