Rolling a Dice

There is a map of size $N \times M$. The right side of the map is east and the top is north. A cell of the map is written as $(r, c)$, where $r$ is the number of cells away from the north edge and $c$ is the number of cells away from the west edge.

A dice is placed on the map. Its net is shown below.

  2
4 1 3
  5
  6

The dice sits at $(x, y)$ with face 1 on top and face 3 facing east. Initially, 0 is written on every face of the dice.

Each cell of the map holds one integer. When the dice rolls onto a cell and the number in that cell is 0, the number on the bottom face of the dice is copied into the cell. Otherwise, the number in the cell is copied onto the bottom face of the dice, and the number in the cell becomes 0.

Given the starting position of the dice and a sequence of move commands, write a program that prints the number on the top face of the dice after every move.

The dice cannot move off the map. A command that would move it off the map is ignored, and nothing is printed for it.

The first line contains the height $N$ and width $M$ of the map ($1 \le N, M \le 20$), the starting coordinates $x$ and $y$ of the dice ($0 \le x \le N-1$, $0 \le y \le M-1$), and the number of commands $K$ ($1 \le K \le 1\,000$).

Each of the next $N$ lines contains the numbers written on one row of the map, rows ordered from north to south and each row listed from west to east. The cell where the dice starts always holds 0. Every cell holds an integer from 0 to 9.

The last line contains the move commands in order: 1 is east, 2 is west, 3 is north, and 4 is south.

After every move, print the number on the top face of the dice on its own line. A command that would move the dice off the map is ignored, and nothing is printed for it.