SPIDY  Spiderman vs Sandman
There is a faceoff between Spiderman & 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 ie: 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 (ie: 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 Testcases follow. Each testcase contains 3 lines.
First line of input contains two space seperated integers H & 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 (i1) 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 testcase 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 <= 10^5
Example
Input:
2
7 3
XX
XXX
6 2
XX
XXX
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.
hide comments
enigmus:
20160217 13:53:21
My god, this problem gave me headaches. Be advised to consider these examples:


hodobox:
20151212 00:33:46
Just a little clarification (cause I got WA for misunderstanding): windows are at heights 0 to H1, Spiderman escapes if he reaches a point beyond the buildings. 

Malena:
20140209 21:26:29
Any Special test cases :P


technophyle:
20130203 15:20:04
Finally AC ;)


Prajwal A N:
20130203 15:20:04
In the problem statement the 3rd kind of move of superman states that


Piyush Kumar:
20130203 15:20:04
Chowshing 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. 

Zhouxing Shi:
20130203 15:20:04
copied from codeforces~~~~ 

Archit Mittal:
20130203 15:20:04
AC...question is a little tricky :) Last edit: 20120925 06:03:14 

Piyush Kumar:
20130203 15:20:04
@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 > hk) 
Added by:  Anil Shanbhag 
Date:  20120920 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  codeforces 