With the rapid development of artificial intelligence, robots today can participate in battles. Consider that in an `xy`-plane, there are `n` bombs are located at coordinates (`x _{i}`,

The program contains a main procedure M and a subroutine S. There are three following types of instructions, where 0 ≤ `k` ≤ 1000000:

- F(
`k`): go forward`k`step; - R(
`k`): turn right 90 degree for`k`times; - S(
`k`): repeat subroutine S for`k`times.

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.

First 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}`,

For 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.

提交代码