SPIDY - Spiderman vs Sandman

There is a faceoff between Spiderman and Sandman.

There are two glass buildings each of height H. Each building has H equal sized windows on the outside covering entire space from bottom to top. Some windows are open and Spiderman cannot land on these window.

In one step, Spiderman can:

  1. Rise up to just above window of the same building he is on.
  2. Slide down to just below window of the same building he is on.
  3. Use his web to jump to Kth window above from current height on the other building.

Sandman on the other rises steadily a rate of 1 per step.

For the purpose of this problem, assume Spiderman and Sandman take turns i.e. Spiderman takes one step, then Sandman takes one step.

Your goal is to assist Spiderman to always remain above or at same height as Sandman at the end of Sandman's turn. Spiderman gets the first turn and both start at height 0 (i.e. Sandman is on the ground and Spiderman is on the window of lowermost floor of left building. It is guarenteed that window of lowermost floor of left building is not open.

Note: If Spiderman gets to area with height >= H assume he has got out.

You are Spiderman's best friend, your duty is to guide Spiderman to escape from Sandman if possible in shortest number of steps to get out.

Input

First line contains integer T.

T test cases follow. Each test case contains 3 lines.

First line of input contains two space separated integers H and K

Next two lines contain description of two buildings.

2nd line represents the left building - a string of length H. The ith character represents the state of window between (i-1) and i heights: character '-' represents closed window (safe to land on), character 'X' represents open window.

Similarly 3rd line represents the right building.

Output

For every test case output single integer x where x is the number of steps taken to get out of building. Output "NO" if Spiderman cannot escape the area and has to fight in the enclosure.

Constraints

1 <= T <= 10

1 <= H, K <= 105

Example

Input:
2
7 3
---X--X
-X--XX-
6 2
--X-X-
X--XX-

Output:
4
NO

Explanation

In first case Spiderman jumps to right building, goes one height down, jumps to left building and jumps to right buidling (he got to the top).

In second case, no matter how he moves, Spiderman cannot escape above the buildings.


Added by:Anil Shanbhag
Date:2012-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:codeforces

hide comments
2016-02-17 13:53:21 enigmus
My god, this problem gave me headaches. Be advised to consider these examples:
(10, 3)
-------x-x
xxx-x-x-xx
Answear: 5

(8, 3)
---xxxxx
xxx-x-xx
Answear: 4

Good luck!

Last edit: 2016-02-17 13:53:45
2015-12-12 00:33:46
Just a little clarification (cause I got WA for misunderstanding): windows are at heights 0 to H-1, Spiderman escapes if he reaches a point beyond the buildings.
2014-02-09 21:26:29 Malena
Any Special test cases :P
2013-02-03 15:20:04 technophyle
Finally AC ;)
I was printing 'YES' instead of actual distance. :p
RE: Don't be too codeforcy :P

Last edit: 2013-06-04 06:50:25
2013-02-03 15:20:04 Prajwal A N
In the problem statement the 3rd kind of move of superman states that
"3. Use his web to jump to Kth window above from current height on the other building."
If spiderman is on ith window (i=1,2,...,h) then is he at height i-1 or at height i?
If he is at height i-1 (as the statement - "Spiderman gets the first turn and both start at height 0, ie: Sandman is on the ground and Spiderman is on the window of lowermost floor of left building."), then how can spiderman climb down a window in the first testcase after jumping to the 3rd window on the right building.
If he is at height i then the answer for the second test case should be 5.
Can someone clarify if the question is wrong or am I going wrong somewhere.
2013-02-03 15:20:04 Piyush Kumar
Chow-shing Shi :: The idea is from there, I agree. But the problem was used as a tutorial for graph algorithms as a practice for upcoming ACM ICPC in an institutional contest, and the problem provided an excellent source for the same. Nonetheless, problem description, output values, and test cases have been kept different.
2013-02-03 15:20:04 Zhouxing Shi
copied from codeforces~~~~
2013-02-03 15:20:04 Archit Mittal
AC...question is a little tricky :)

Last edit: 2012-09-25 06:03:14
2013-02-03 15:20:04 Piyush Kumar
@dexter: consider him escaped if he jumps to height > h (as a result of a one unit jump from height h or from a k unit jump from opposite building from height > h-k)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.