Красный и синий роботы находятся в разных целочисленных точках плоскости. У каждого робота есть пульт с записанной последовательностью из $$$n$$$ команд.
Каждая команда перемещает робота на одну клетку:
Изначально красный робот держит первый пульт, а синий - второй.
В секунду $$$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.
В первой строке выведите конечные координаты красного робота.
Во второй строке выведите конечные координаты синего робота.
30 0 2 0RRULLU
0 1 2 1
30 0 2 0RUULUR
1 2 2 1
20 0 1 0RULD
1 1 0 -1
В первом примере после первой секунды оба робота оказываются в точке $$$(1,0)$$$ и обмениваются пультами. Во вторую секунду красный робот выполняет команду L со второго пульта, а синий - команду R с первого. В третью секунду оба выполняют команду U.
Во втором примере роботы встречаются после первой и после второй секунды. Они дважды обмениваются пультами, поэтому третью команду каждый выполняет со своего исходного пульта.
В третьем примере после первой секунды роботы меняются позициями. Это не считается встречей, поэтому пульты остаются у прежних владельцев.
