Robot Rescue

Time Limit: 2 Seconds

Memory Limit: 65536 KB

Description

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 (xi, yi) for i = 1, 2, ..., n, where the x-axis points horizontally to the right, and the y-axis 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:

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

The main procedure M can contain all the three types of instructions, while the subroutine S can contain only instructions F(k) and R(k) but not S(k). See Figure 3 for an example.

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.

Input

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 x1, y1, x2, y2, ..., xn, yn, 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.

Output

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.

Sample Input

2
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 Output

0
1

Hint

None

Source

None

提交代码