Professor Mahir is developing some AI using some famous sitcom characters’ characteristics. The most interesting part is that he has created some robots and filled their brains with those characters. He wants to demonstrate his 1st prototypes. For this, he also invites Comedian Redoan. Dr. Mahir starts the conversation with the robots,
Dr. Mahir: I am always angry! What can you propose?
Barney Stinson: Let’s go to Area 51 and everybody suits up.
Chandler Bing: So, you set up a meeting with aliens. Could you be more stupid?
Sheldon Cooper: Penny, Area 51 is the common name of a highly classified United….
Penny: I know, I saw 2-hour boring documentation on this with Leonard forcefully.
(Sheldon Cooper bot crashes. Penney should let him finish)
Jake Harper: Can we get aliens food also there?
Dr. Mahir stopped all the robots and start trying to fix the Sheldon bot. But Redoan has another cunning plan. He thinks that if he gets those robots to his house then the bots can help him to prepare his stand-up comedy scripts because his jokes are not funny anymore and he cannot generate new puns. So, he stoles the robots without Sheldon bot.Later Dr. Mahir notices this and informs this to crazy detective Shibli.
Shibli knows when Redoan will go to the stage for his show and come back to his house. So Shibli wants to go to Redoan's house immediately when he leaves the house and want to get those robots before Redoan comes back. D is the duration (in minute) between Redoan leaves the house and comes back.
You can imagine Redoan's house as a 2d grid with NxM cells. (0,0) is the top left corner and (N-1, M-1) is the bottom right. Each cell is either empty or contains Redoan’s clothes or the robots. You cannot go to a cell that conains Redoan's clothes. You can assume that all the robots are on the same cell.
Shibli will always enter through the door which is in (0, 0) cell. You can assume that (0, 0) cell is always empty. He can immediately go to any adjacent cell without wasting any time. He also can jump to an empty cell if the distance between that cell and the current cell is less than or equal to K but in order to do that, he will take full 1 minute to prepare and complete his jump. To get the robots he needs to go to any adjacent cell of the robot containing cell.
Two cells are adjacent if they share any corner or side.
Input
At first, there will be an integer T (1<=T<=3), which is the number of test cases. The first line of each test case contains four integers N, M, K and D, separated by spaces, with 1 ≤ N, M ≤ 100, 2 <= K <= 50, 1 <= D <= 100000. The following N lines of the each test case will contain one row of the maze. Each of these lines contains exactly M characters, and each of these characters is one of the following:
# denotes Redoan’s clothes
. (dot) denotes an empty cell
R denotes the cell where all the robots are
For better understanding, see the sample I/O.
Output
For each case, print YES if Shibli can get the robots without getting caught otherwise NO.
Sample
| Input | Output |
|---|---|
2 4 4 4 10 .... ..#. .... ..R. 4 4 4 10 .... ###. #R#. ###. | YES NO |
