H. Crawling
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Veronica learned to crawl, and now she needs to be carefully watched.

Igor and Ira allow her to crawl on a large mat in the room; the mat is a large rectangle with dimensions $$$n$$$ by $$$m$$$. Initially, Veronica is located somewhere on the mat and looks down in the direction of the «V» symbol. Veronica is not allowed to leave the mat and crawl on the floor.

Veronica can move on the mat only to neighboring cells and only in the direction in which she is looking. To move to the next cell, Veronica will need to spend $$$f$$$ seconds; also, Veronica can turn clockwise by $$$90$$$ degrees in $$$r$$$ seconds and turn counterclockwise by $$$90$$$ degrees in $$$l$$$ seconds.

There are several toys «*» scattered on the mat that Veronica is interested in, and several obstacles that she cannot pass or remove «$$$\#$$$»; if the cell is empty, then it is designated «.». Veronica really wants to crawl to some of her toys; it is assumed that Veronica reaches the toy if she lies in the next cell from the toy and looks in the direction of the toy.

Igor and Ira know by experience that if Veronica does not crawl to the toy in $$$t$$$ seconds, she will cry and must be picked up.

Help Igor, Ira and Veronica determine whether Veronica will be able to crawl to any toy or not.

Input

The first line contains six integers $$$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)$$$ – the width and length of the mat, the number of seconds for Veronica to turn in place clockwise and counterclockwise by $$$90$$$ degrees, the number of seconds for Veronica to move one square forward, the number of seconds that Veronica can move.

Further, a mat is given in $$$n$$$ lines, and each line has a length of $$$m$$$. All lines consist of the characters «.» – the cell is empty, «$$$\#$$$» – there is an insurmountable obstacle in the cell, «*» – there is a toy in the cell, «V» – a symbol of Veronica's location showing her original direction.

Veronica is guaranteed to be positioned correctly on the mat, and the symbol «V» occurs exactly once.

Output

Output «YES» if Veronica manages to reach a toy; otherwise, output «NO».

Examples
Input
4 4 10 10 10 70
....
..V.
###.
.*..
Output
YES
Input
4 4 5 5 10 24
....
..V.
....
.*..
Output
NO