
ZOJ Problem Set  3973
With the rapid development of artificial intelligence, robots today can participate in battles. Consider that in an xyplane, there are n bombs are located at coordinates (x_{i}, y_{i}) for i = 1, 2, ..., n, where the xaxis points horizontally to the right, and the yaxis points vertically upwards. A robot is initially located at coordinate (0, 0), and facing upwards. A commander, Owen, has developed a program of instructions for the robot to move, so that the robot can be rescued from the bombs and reach a destination at (a, b). The program contains a main procedure M and a subroutine S. There are three following types of instructions, where 0 ≤ k ≤ 1000000:
Figure 3. An illustrate example with n = 2 bombs located at (0, 1) and (1, 1), where the robot can reach the destination (6, 3) by following a program with a main procedure M that consists of instructions R(1), F(1), S(3), and F(2), and with a subroutine S that consists of instructions, F(1), R(1), F(1), and R(3). Given a main procedure M and a subroutine S, represented by two strings with spaces to separate instructions, your task is to help Owen determine whether or not by following the program, the robot will reach the destination at (a, b) without moving to any bomb. InputFirst line of the input is an integer T indicating the number of test cases. For each case, the first line contains two integers a and b, representing the coordinate of the destination. The second line contains an integer n, followed by n pairs of integers x_{1}, y_{1}, x_{2}, y_{2}, ..., x_{n}, y_{n}, representing the coordinates for the n bombs, where 1 ≤ n ≤ 10000. The third line contains a string of instructions for the main procedure M, and the fourth line contains a string of instructions for the subroutine S, where instructions are separated by spaces, and the length of each string is less than 1000. OutputFor each case, if the robot reaches the destination at (a, b) without moving to any bomb, then output 0, otherwise, if the robot moves to any bomb, then output an integer representing the first bomb that the robot has moved to, otherwise, output 1. Sample Input2 6 3 2 0 1 1 1 R(1) F(1) S(3) F(2) F(1) R(1) F(1) R(3) 100 20 2 0 1 1 1 R(2) S(20) F(80) F(1) R(3) F(1) R(1) Sample Output0 1 Source: ACM Collegiate Programming Contest 2017 (Hong Kong) 