Лоренцо считается одним из самых выдающихся дизайнеров одежды за последние тысячу лет. Совсем недавно, Лоренцо представил свое новое, по истине гениальное творение, жемчужину в сфере моды. Он разработал костюм, целиком сшитый из липучки. Костюм настолько уникальный, что ни один дизайнер еще не представлял что-либо подобное. К сожалению, костюм оказался не совсем практичным. Когда Лоренцо направлялся на выставку одежды, он решил сэкономить, и вместо такси бизнес-класса решил заказать эконом. В результате, его костюм прилип к тканевому салону автомобиля, и Лоренцо потребовалась помощь водителя, чтобы выбраться из машины. Справившись с этой сложностью, внезапно возникла другая. Как оказалось, на выставке, некоторые из перегородок были покрыты тканью, и прислонившись к одной из них, Лоренцо опять прилип. Теперь он может передвигаться только тремя способами: вращаться по часовой стрелке, вращаться против часовой стрелки, либо попробовать изо всех сил оттолкнуться от перегородки, в результате чего, Лоренцо будет лететь перпендикулярно поверхности стены до тех пор, пока не врежется в другую стену, либо не вылетит за пределы выставки. Чтобы справиться и с этой трудностью, ему необходимо либо попасть на обычную перегородку (не покрытую тканью), либо вылететь за пределы выставки. Обратите внимание, что если Лоренцо прилип к стене снаружи выставки, то это не означает, что он вылетел за её пределы. К сожалению, с момента как он покинул такси, у Лоренцо осталось не очень много сил, поэтому он хочет совершить минимальное количество движений, чтобы выбраться из этой ситуации. Он решил обратиться к вам за помощью и попросил разработать план, в результате которого он снова сможет свободно перемещаться (не прислоняясь к стене).
У вас есть план выставки, представляющий из себя клетчатое поле размером $$$w$$$ клеток в ширину и $$$h$$$ клеток в высоту. Клетки пронумерованы сверху вниз, слева направо, начиная с единицы. На границах клеток могут стоять перегородки. Известно, что всего есть $$$n$$$ перегородок покрытых тканью (липких) и $$$m$$$ обычных (не липких). Вам известно, к какой перегородке с какой стороны прилип Лоренцо. Вам необходимо найти минимальное количество действий, выполняя которые, Лоренцо сможет свободно перемещаться. Всего существует три вида действий:
Рисунок 1. Примеры возможных действий В первой строке задано четыре целых числа $$$w$$$, $$$h$$$, $$$n$$$ и $$$m$$$ — ширина и высота выставки, а также количество перегородок покрытых тканью и обычных перегородок соответственно.
В следующих $$$n$$$ строках задано два целых числа $$$x$$$ ($$$1 \le x \le w$$$) и $$$y$$$ ($$$1 \le y \le h$$$) и один символ $$$t$$$ — координаты клетки и ее граница, на которой расположена липкая перегородка. Символ $$$L$$$ означает, что перегородка расположена на левой границе, $$$R$$$ — на правой, $$$U$$$ — на верхней и $$$D$$$ — на нижней.
В следующих $$$m$$$ строках задано описание обычных перегородок в таком же формате.
В последней строке задано два целых числа $$$sx$$$ ($$$1 \le sx \le w$$$) и $$$sy$$$ ($$$1 \le sy \le h$$$) и один символ $$$st$$$ — координаты клетки и ее граница, к которой прилип Лоренцо. Гарантируется, что Лоренцо прилип к стене, покрытой тканью.
Гарантируется, что каждая стена не может быть одновременно липкой и обычной (даже различные стороны). Также обратите внимание, что например «1 1 D» и «1 2 U» описывают одну и ту же стену.
$$$$$$1 \le w, h \le 10^5$$$$$$ $$$$$$1 \le n \le 5 \cdot 10^5$$$$$$ $$$$$$0 \le m \le 5 \cdot 10^5$$$$$$ $$$$$$n + m \le 5 \cdot 10^5$$$$$$
В первой строке выведите «No», если Лоренцо не сможет освободиться.
В противном случае в первой строке выведите «Yes», а в следующей строке выведите строку, описание маршрута Лоренцо.
Символ «>» означает поворот по часовой стрелке, «<» — против часовой стрелки, а «^{}» означает, что Лоренцо необходимо оттолкнуться от стены. Если существует несколько вариантов ответа, вам необходимо вывести любой, состоящий из наименьшего числа действий.
1 1 3 11 1 L1 1 R1 1 D1 1 U1 1 D
Yes ^
1 1 3 11 1 L1 1 R1 1 D1 1 U1 1 L
Yes <
2 2 8 01 1 U2 1 U1 1 L1 2 L2 1 R2 2 R2 2 D1 1 D1 1 U
Yes ^>^
1 1 3 01 1 U1 1 D1 1 L1 1 D
Yes >^
1 1 4 01 1 U1 1 D1 1 L1 1 R1 1 L
No
Рисунок 2. Визуализация для тестовых примеров 1-3
| BSUIR Open XII: Student final |
|---|
| Закончено |
