Вероника научилась ползать, теперь за ней нужен глаз да глаз.
Игорь и Ира разрешают ей ползать на большом мате в комнате, сам мат представляет из себя большой прямоугольник размером $$$n$$$ на $$$m$$$. Изначально Вероника расположена где-то на мате и смотрит вниз, по направлению символа «V». Веронике запрещено покидать мат и ползать по полу.
Вероника может перемещаться на мате только в соседние клеточки и только в направлении, в которое она смотрит. Для того, чтобы переместиться на соседнюю клеточку, Веронике потребуется потратить $$$f$$$ секунд, также Вероника может повернуться по часовой стрелке на $$$90$$$ градусов за $$$r$$$ секунд и повернуться против часовой стрелки на $$$90$$$ градусов за $$$l$$$ секунд.
На мате разбросаны несколько игрушек «*», которые Веронике интересны, и ряд препятствий, которые непреодолимы и которые она не может убрать «$$$\#$$$», если клеточка пустая, то она обозначается «.». Вероника очень хочет доползти до какой-нибудь своей игрушки, считается, что Вероника доползла до игрушки, если она лежит в соседней клетке от игрушки и смотрит в направлении игрушки.
Игорь и Ира знают опытным путем, что если Вероника не успеет доползти до игрушки за $$$t$$$ секунд, тогда она расплачется и ее придется брать на ручки.
Помогите Игорю, Ире и Веронике определить сможет ли Вероника доползти до какой-нибудь игрушки или нет.
В первой строке задано шесть целых чисел $$$n$$$, $$$m$$$, $$$l$$$, $$$r$$$, $$$f$$$, $$$t$$$ $$$(1\leq n,m \leq 10^3, 1\leq l,r,f \leq 100,1\leq t\leq 10^6)$$$ — ширина и длина мата, количество секунд, чтобы Вероника повернулась на месте по часовой и против часовой стрелке на $$$90$$$ градусов, количество секунд, чтобы Вероника передвинулась на одну клеточку вперед, количество секунд, которое Вероника готова передвигаться.
Далее в $$$n$$$ строках задан мат, каждая строка имеет длину $$$m$$$. Все строки состоят из символов «.» — клетка пустая, «$$$\#$$$» — в клетке лежит непреодолимое препятствие, «*» — в клетке есть игрушка, «V» — символ расположения Вероники и показывающий ее изначальное направление.
Гарантируется, что Вероника расположена корректно на мате и символ «V» встречается ровно один раз.
Выведите «YES», если Вероника успеет добраться до какой-нибудь игрушки, в противном случае выведите «NO».
4 4 10 10 10 70 .... ..V. ###. .*..
YES
4 4 5 5 10 24 .... ..V. .... .*..
NO
