3.2 Scholar Shweta

Score: 60pts

Time Limit: 1.00 sec

An engineer named Shweta designed a robot that moves when a signal is transmitted to it, this signal is in the form of a string containing the characters "U", "D", "L" and "R" that would move the robot up, down, left and right respectively. The robot is designed in such a way that it moves 1 unit of distance per operation. She wants that the robot should only move from vertex to vertex inside a grid of size \(n\) x \(m\) so she started looking for a solution. In order to optimize her solution, she ran some tests and now she wants to analyse the data from them. She wants to know that for a particular signal how many times does the robot exit and enter the grid and also wants to know will the robot be inside or outside the grid after performing all the operations. Help her get the desired data for a given signal.

Constraints

\(1 \leq n \lt 10^{6}\)

\(1 \leq m \leq 10^{6}\)

\(1 \leq k \leq 9000\)

\(1 \leq x \leq n\)

\(1 \leq y \leq m\)

\(1 \leq m \leq 10^{6}\)

\(1 \leq k \leq 9000\)

\(1 \leq x \leq n\)

\(1 \leq y \leq m\)

Input Format

The first line contains three space-separated integers, \(n\), \(m\), \(k\). \(n\) and \(m\) represents the size of the grid, \(k\) represents the number of operations that the robot will perform.

The next line contains two space-separated integers \(x\) and \(y\) which denote the starting point of the robot.

The next line contains a string of length \(k\), each character of that string represents an operation.

The next line contains two space-separated integers \(x\) and \(y\) which denote the starting point of the robot.

The next line contains a string of length \(k\), each character of that string represents an operation.

Output Format

Print the number of times the robot exits and enters the grid and the final position of the robot after performing all of the operations, “IN” if the robot is inside the grid and “OUT” if it is outside.

Example 1

Input:

4 4 5

1 4

URDLU

Output:

1 OUT

Explanation:

The robot goes up so the coordinates are (1, 5) so the robot is out of the grid, on operation “R” coordinates are (2, 5), on operation “D” coordinates are (2, 4) so here the robot came back into the grid. After executing other 2 operations the position of the robot is (1, 5) which is OUT, but we are only counting the number of times the robot has exited and entered the grid so total is 1.

4 4 5

1 4

URDLU

Output:

1 OUT

Explanation:

The robot goes up so the coordinates are (1, 5) so the robot is out of the grid, on operation “R” coordinates are (2, 5), on operation “D” coordinates are (2, 4) so here the robot came back into the grid. After executing other 2 operations the position of the robot is (1, 5) which is OUT, but we are only counting the number of times the robot has exited and entered the grid so total is 1.

Example 2

Input:

3 5 6

2 3

RRDLUU

Output:

1 IN

Explanation:

The robot goes right twice so the coordinates are (4, 3) so the robot is out of the grid, on operation “D” coordinates are (4, 2), on operation “L” coordinates are (3, 2) so here the robot came back into the grid. After executing the next two operations the position of the robot is (4, 4) which is IN, so the robot entered and exited the grid only once.

3 5 6

2 3

RRDLUU

Output:

1 IN

Explanation:

The robot goes right twice so the coordinates are (4, 3) so the robot is out of the grid, on operation “D” coordinates are (4, 2), on operation “L” coordinates are (3, 2) so here the robot came back into the grid. After executing the next two operations the position of the robot is (4, 4) which is IN, so the robot entered and exited the grid only once.