Walking Robot Simulation

A robot on an infinite XY-plane starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands (given in the COMMANDS array/list):

1) -2: turn left 90 degrees,

2) -1: turn right 90 degrees, or

3) 1 <= ‘K’ <= 9: move forward K units.

Some of the grid squares are obstacles. The ‘ith’ obstacle is at grid point OBSTACLES[i] = (Xi, Yi).

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the maximum Euclidean distance that the robot will be from the origin squared (i.e. if the distance is 5, return 25).

Note :

North means +Y direction.
East means +X direction.
South means -Y direction.
West means -X direction.

For example:

N = 1, M = 0 
COMMANDS = [3], OBSTACLES = []

The final answer would be 9 since it moves 3 steps north.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’, ‘M’ Where ‘N’ is the number of COMMANDS and ‘M’ is the number of OBSTACLES.

The next line contains ‘N’ space-separated integers denoting the commands.

The next M lines contain two space-separated integers ‘X’ and ‘Y’, denoting the coordinates of obstacles.

Output format :

For each test case, return the distance the robot covers. The output of each test case will be printed in a separate line[0-based indexing].

Note:

You don't have to print anything, just implement the function.

Constraints:

1 <= T <= 5
1 <= N <= 10^3
1 <= M <= 10^3
-2 <= COMMANDS[i] <= 9
-3 * 10 ^ 3 <= OBSTACLES[i][j] <= 3 * 10 ^ 3

Time limit: 1 second