PUCMM004 - Moving the dog around
You want to increase the stamina of your puppy. Therefore you set up a n × m grid and marked each 1 × 1 unit with a red marker. In the past you trained your dog to move certain steps in a specified cardinal direction. That is, the dog is able to move a certain number of steps NORTH, SOUTH, EAST and WEST. You think that if you make your lazy puppy move around in the grid, he’ll eventually gain stamina and thus become a more proper dog. Please note the dog cannot step out of the grid at any time.
One day you gave your dog a sequence of commands and eventually ended up at position (x, y). You think (x, y) is a very odd position and wonder how that happened. Of course, you forgot where you started from.
Given the sequence of commands that led the dog to its final position, find out where the dog started from.
Input
The first line of input contains two space-separated positive integers n and m (1 <= n, m <= 50). The second line of the input contains three space-separated positive integers x, y (1 <= x <= n, 1 <= y <= m) and count (0 <= count <= 100000). They are, respectively, the row and column coordinates of the final position, as well as the number of commands you gave the dog. Then there are count lines. Each of these lines contain the i-th command. The i-th command is a space-separated pair of the cardinal position (a character N (North), S (South), E (East), W (West)) and a positive integer steps representing how many steps to take in that direction. It is guaranteed that no command will ever force the dog outside the boundaries of the grid. Also, please note that these lines are given in order. That is, the first line corresponds to the first command you gave the dog, not the last one.
Output
Output two space-separated positive integers representing the coordinate of the starting position.
Example
Input: 3 3 3 3 5 E 1 S 1 W 1 S 1 E 2 Output: 1 1
Below is an illustration of the dog’s path.
Added by: | kojak_ |
Date: | 2013-03-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | 2013 PUCMM Beginners (Round #1) |