Description

Oh no! You got electrocuted by spilling coffee on your laptop and you are now reincarnated as a Roomba. You look at your surroundings, and it's a normal living room, but it's dirty. As a good Roomba, you need to help your owner clean it up. Your owner is bossy, so he just tells you the living room's grid dimension and the direction of the path you need to take.

You have a bumper sensor, so when a command would put you outside the room, you refuse to move and wait for the next one. Every tile you enter gets cleaned, and you keep a running total of everything you've absorbed. Here are the exact rules:

• The room is a grid of R rows and C columns. Rows and columns are 0-indexed; row 0 is the top (north) and column 0 is the left (west).
• If a command would take you outside of the room, you do not move at all, you skip the command and you go on to read the next command.
• If you receive the command STOP, your shift ends immediately. Every command after STOP counts as skipped. STOP itself is not counted.
• If the commands run out, your shift has ended.
• When you move the full <steps> tiles, you clean every tile you pass through, including the one you land on. You absorb that tile's dirt, and it becomes 0. Your starting tile is not cleaned at the start of the shift; you only clean tiles you enter.
• At the end of your shift, report your final location, the total dirt you absorbed, and how many commands you skipped.

Note: Crash Course about Loop: https://hackmd.io/@gladysvalerie/S1wWLYCYze

Input

In the first line, you will input five integers: com R C sr sc . com is the number of commands you will receive from your owner, R C are the dimension of the room’s grid size, sr sc are your starting point in the grid.

The next R lines describe the room: C digits each, where each digit (0-9) is that tile’s dirt level.

The next com lines are each either <dir> <steps>, where <dir> is one of N, S, E, W and <steps> is a positive integer, or the single word STOP.

Constraints

• 1 ≤ com ≤ 100
• 1 ≤ R, C ≤ 100
• 0 ≤ sr < R, 0 ≤ sc < C (the start is always inside the room)
• Each tile's dirt level is a single digit, 0–9
• <dir> is one of N, S, E, W
• 1 ≤ <steps> ≤ 100
• Each command is either <dir> <steps> or STOP, and there are exactly com of them

Output

In the first line, output your final position fr fc final row and final column.

The second line, output the total dirt you collected.

The third line, output the number of commands skipped.

Sample Input  Download

Sample Output  Download

Discuss