Kids in a Grid

Two kids are walking in a H × W grid. Each square in the grid contains a character (whose ASCII code lies between 33 and 127). Both kids can move north, east, west and south each step. The first kid walked N steps, the second kid walked M steps. (0 ≤ N ≤ M ≤ 20000). If we write down all the characters each kid walks on, we get two strings SA and SB. your task is to delete as few characters as possible, so that the two new strings are the same. Input the first line contains a single integer t (1 ≤ t ≤ 15), the number of test cases. Each test case contains several lines. The first line contains two integers H and W (1 ≤ H, W ≤ 20), the next H lines contains the grid. Next line contains three integers N, X0 and Y0 ( 1 ≤ X0 ≤ H,1 ≤ Y0 ≤ W,X increases from North to South, while Y increases from West to East), indicating the first kinds walks from (X0,Y0), for N steps. The next line contains a string of N characters, N, E, W, S stands for North, West, South and East, respectively. The second kid’s information follows, which is the same format. You may assume the walk sequence is correct: they will never go outside the grid. Output For each case, print the case number and two integers XA and XB, indicating the number of characters deleted from SA and SB, respectively. Note: In the first sample, SA = ABCDG, SB = ADEB, we must delete 3 characters from SA and 2 from SB, so that they are the same (both AB or AD) Sample Input 2 34 ABCD DEFG ABCD 411 EEES 331 NES 34 ABCD DEFG ABCD 411 EEES 331 NES Sample Output Case 1: 3 2 Case 2: 3 2