If you’re on a highway and Road Runner goes “beep beep” just step aside or you might end up in a heap. Road Runner, Road Runner runs on the road all day. Even the Coyote can’t make him change his ways. — The Road Runner Show theme song — The Road Runner (Accelleratii incredibus) is a very fast-running ground bird which can be found in the roads of the hot and lonely Southwestern United States. Wile E. Coyote (Carnivorous vulgaris), a clever canine, has repeatedly and unsuccessfully tried to catch it using every kind of trap imaginable. The Interstate is the Road Runner’s favourite road, since it’s a straight, L miles long path along which it can run at constant speed without stopping or turning. One particular summer day, the Road Runner is sunbathing on the Interstate and wants to run home (also on the Interstate) in exactly m minutes, never exceeding v miles per minute. The Coyote meanwhile has installed bombs at certain positions along the road and programmed them to go off at certain times in the hopes of catching the Road Runner in one of the explosions. Every minute, the Road Runner can move an integer amount of miles which must be less than or equal to v, avoiding the spots in the road which have a bomb programmed to go off during that minute. Given the positions of the bombs which will go off each minute, you must calculate the minimum amout of miles the Road Runner must move to go from its sunbathing spot to its home in exactly m minutes, avoiding all explosions. Input The input consists of several test cases. Each case begins with a line with a positive integer L which is the length of the Interstate in miles (1 ≤ L ≤ 1000). Then follows a line with two integers xi and xf which are, respectively, the initial position of the Road Runner and the location of its home (0 ≤ xi ≤ L, 0 ≤ xf ≤ L). The next line contains two integers m and v which represent, respectively, the amount of minutes in which the Road Runner wants to reach its home and the maximum allowed velocity in milesperminute(1≤m≤100,1≤v≤L). EachoneofthenextmlinescontainsastringofL+1 characters; character i of line j is ‘X’ if there is a bomb at position i which will go off during the jth minute, or ‘.’ otherwise. You may assume that no bomb will go off at position xi during the first minute. The end of the input is given by L = 0, which should not be processed as a test case. Output For each test case output a line with the minimum amount of miles the Road Runner must move to go home in exactly m minutes and avoiding all explosions. If it is not possible for the Road Runner to go home avoiding all explosions, then output ‘-1’. Sample Input 6 06 56 ...X... XX..XX.
2/2 ...X... .XX.... ....... 6 06 55 ...X... XX..XX. ...X... .XX.... ....... 6 16 33 ....... ...X... ....... 6 16 32 ....... ...X... ....... 0 Sample Output 10 -1 5 -1