Wiggle Walk solution kickstart

Wiggle Walk solution kickstart- Banny has just bought a new programmable robot. Eager to test his coding skills, he has placed the robot in a grid of squares with RR rows (numbered 11 to RR from north to south) and CC columns (numbered 11 to CC from west to east). The square in row rr and column cc is denoted (r,c)(r,c).

Initially the robot starts in the square (SRSR, SCSC). Banny will give the robot NN instructions. Each instruction is one of N, S, E, or W, instructing the robot to move one square north, south, east, or west respectively.

If the robot moves into a square that it has been in before, the robot will continue moving in the same direction until it reaches a square that it has not been in before. Banny will never give the robot an instruction that will cause it to move out of the grid.

Can you help Banny determine which square the robot will finish in, after following the NN instructions?

Input

Wiggle Walk solution kickstart

The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case starts with a line containing the five integers NN, RR, CC, SRSR, and SCSC, the number of instructions, the number of rows, the number of columns, the robot’s starting row, and the robot’s starting column, respectively.

Then, another line follows containing a single string consisting of NN characters; the ii-th of these characters is the ii-th instruction Banny gives the robot (one of N, S, E, or W, as described above).

Output

For each test case, output one line containing Case #xx: rr cc, where xx is the test case number (starting from 1), rr is the row the robot finishes in, and cc is the column the robot finishes in.

Limits

Memory limit: 1 GB.
1≤T≤1001≤T≤100.
1≤R≤5×1041≤R≤5×104.
1≤C≤5×1041≤C≤5×104.
1≤SR≤R1≤SR≤R.
1≤SC≤C1≤SC≤C.
The instructions will not cause the robot to move out of the grid.

Test Set 1

Time limit: 20 seconds.

1≤N≤1001≤N≤100.

Wiggle Walk solution kickstart

Test Set 2

Time limit: 60 seconds.

1≤N≤5×1041≤N≤5×104.

Sample

3
5 3 6 2 3
EEWNS
4 3 3 1 1
SESE
11 5 8 3 4
NEESSWWNESE

Case #1: 3 2
Case #2: 3 3
Case #3: 3 7

Sample Case #1 corresponds to the top-left diagram, Sample Case #2 corresponds to the top-right diagram, and Sample Case #3 corresponds to the lower diagram. In each diagram, the yellow square is the square the robot starts in, while the green square is the square the robot finishes in.