Pixel Shuffle

Shuffling the pixels of a bitmap image can produce a random-looking picture. Yet if you repeat the same shuffle enough times, the original image eventually reappears. This is no surprise: a "shuffle" is a one-to-one mapping (a permutation) of the finitely many cells of the image, so iterating it must return to the start.

Your program reads a number $n$ and a list of elementary transformations that together define a shuffle $\varphi$ of $n \times n$ images. It must compute the smallest number $m$ (with $m > 0$) such that applying $\varphi$ exactly $m$ times always reproduces the original $n \times n$ image.

For example, if $\varphi$ is a counter-clockwise $90^\circ$ rotation, then $m = 4$.

The input consists of two lines.

The first line contains the number $n$ ($2 \le n \le 1024$, and $n$ is even). An image is stored as an $n \times n$ pixel matrix $(a_{i,j})$, where $i$ is the row index and $j$ is the column index. The upper-left pixel is at row $0$, column $0$.

The second line is a non-empty list of at most $32$ words separated by spaces. A valid word is one of the keywords id, rot, sym, bhsym, bvsym, div, mix, optionally followed by a -. Each keyword key denotes an elementary transform (defined in Figure 1 below), and key- denotes the inverse of key. For instance, rot- is the inverse of the counter-clockwise $90^\circ$ rotation, that is a clockwise $90^\circ$ rotation.

The list $k_1, k_2, \ldots, k_p$ denotes the compound transform $\varphi = k_1 \circ k_2 \circ \cdots \circ k_p$; that is, $k_p$ is applied first and $k_1$ is applied last. For instance, bvsym rot- first performs a clockwise $90^\circ$ rotation and then a vertical symmetry on the lower half of the image.

Each elementary transform maps an image $(a_{i,j})$ to an image $(b_{i,j})$ as follows.

Transform	Illustration
id — identity. Nothing changes: $b_{i,j} = a_{i,j}$.
rot — counter-clockwise $90^\circ$ rotation: $b_{i,j} = a_{j,\; n-1-i}$.
sym — horizontal symmetry: $b_{i,j} = a_{i,\; n-1-j}$.
bhsym — horizontal symmetry applied to the lower half: if $i \ge n/2$ then $b_{i,j} = a_{i,\; n-1-j}$, otherwise $b_{i,j} = a_{i,j}$.
bvsym — vertical symmetry applied to the lower half: if $i \ge n/2$ then $b_{i,j} = a_{\,3n/2 - 1 - i,\; j}$, otherwise $b_{i,j} = a_{i,j}$.
div — division. Rows $0, 2, \ldots, n-2$ become rows $0, 1, \ldots, n/2 - 1$, while rows $1, 3, \ldots, n-1$ become rows $n/2, n/2 + 1, \ldots, n-1$.
mix — row mix. Rows $2k$ and $2k+1$ are interleaved. Row $2k$ of the new image is $a_{2k,0}, a_{2k+1,0}, a_{2k,1}, a_{2k+1,1}, \ldots, a_{2k,\,n/2-1}, a_{2k+1,\,n/2-1}$, while row $2k+1$ of the new image is $a_{2k,\,n/2}, a_{2k+1,\,n/2}, a_{2k,\,n/2+1}, a_{2k+1,\,n/2+1}, \ldots, a_{2k,\,n-1}, a_{2k+1,\,n-1}$.

Figure 1: how each transform turns image $(a_{i,j})$ into image $(b_{i,j})$.

Output a single line containing the smallest number $m$ ($m > 0$) such that $\varphi^m$ is the identity. You may assume that $m < 2^{31}$ for every test input.