| Codeforces Round 188 (Div. 1) |
|---|
| Закончено |
Юная Принцесса Влада любит прыгать по лужайкам и гулять по лесу. Как-то раз в один замечательный солнечный день во время прогулки Принцесса с удивлением обнаружила, что ее тень куда-то пропала. «Ну и дела», — подумала она и отправилась гулять по лесу в поисках своей тени.
Обычно Тень живет под Принцессой. Но именно в тот самый чрезвычайно солнечный день Тени наскучил однообразный образ жизни, и она решила поиграть с Владой.
Лес, в котором развлекаются наши герои, можно представить как множество целочисленных клеток на плоскости, и перемещаться Тень с Принцессой могут только вверх, вниз, вправо и влево на 1. В некоторых клетках, как и положено лесу, растут деревья. Тень и Принцесса не могут ходить в клетку, где расположено дерево. Стоит отметить, что лес переживает трудные времена. В лесу растет совсем немного деревьев...
В начальный момент времени Принцесса гуляет в клетке с координатами (vx, vy), в то время как Тень спряталась от Принцессы в клетке (sx, sy). Принцесса, Тень и деревья находятся в разных клетках.
Тень играет с Принцессой. Как только Принцесса ходит на 1 в каком-либо направлении, Тень одновременно с Принцессой отлетает на 1 в том же направлении, если это возможно (если клетка, в которую она отлетает, не содержит дерево); в противном случае, Тень остается на своем месте. Тень эфемерна, поэтому наши герои никоим образом не мешают друг другу.
Считается, что Принцесса поймает Тень, если после какого-либо хода она окажется с ней в одной клетке. Владе удалось отыскать свою Тень. А смогли бы Вы?
Первая строка входных данных содержит координаты героев vx, vy, sx, sy и количество деревьев m (0 ≤ m ≤ 400), разделенные пробелом. Следующие m строк содержат координаты деревьев.
Координаты героев и деревьев целые и лежат в границах от -100 до 100 включительно. Принцесса, Тень и деревья расположены в различных клетках.
Если Принцесса никак не сможет поймать Тень, выведите «-1» (без кавычек).
Иначе выведите последовательность символов «L», «R», «D», «U», соответствующих ходам Принцессы, следуя которым, она поймает Тень в некоторой клетке своего пути (L — ход налево, R — направо, U — вверх, D — вниз; ось x направлена вправо, y — вверх).
Количество символов (то есть количество ходов) не должно превышать 106. Все ходы Принцессы должны быть корректны, то есть не могут вести туда, где стоит дерево. Принцессе разрешается вставать с Тенью в одну клетку и до последнего хода.
0 0 1 0 1
0 1
LLUR
5 0 3 0 8
2 -1
2 0
2 1
3 -1
4 1
4 0
3 1
4 -1
-1
3 2 1 1 3
0 1
1 0
0 0
DLL
Ниже приведены картинки к примерам (Принцессе, Тени и деревьям отвечают розовый, серый и черный цвета соответственно; синим цветом помечен центр плоскости).
В первом случае Принцесса может сделать два хода влево, один вверх и один вправо: 
В следующем случае Принцесса не сможет добраться до Тени: 
В данном примере можно сделать два хода влево и один вниз (в любом порядке): 
