픽셀 셔플

비트맵 이미지의 픽셀을 뒤섞으면 무작위처럼 보이는 그림이 만들어질 수 있습니다. 하지만 같은 방식으로 충분히 여러 번 뒤섞으면 결국 원래 이미지가 다시 나타납니다. 이는 놀라운 일이 아닙니다. "섞기(shuffle)"란 이미지를 이루는 유한개의 칸에 대한 일대일 대응(순열)이므로, 이를 반복하면 반드시 처음 상태로 돌아오기 때문입니다.

프로그램은 정수 $n$과, $n \times n$ 이미지에 대한 섞기 $\varphi$를 정의하는 기본 변환들의 목록을 읽습니다. 그런 다음 $\varphi$를 정확히 $m$번 적용하면 항상 원래의 $n \times n$ 이미지가 되는 가장 작은 정수 $m$ ($m > 0$)을 구해야 합니다.

예를 들어 $\varphi$가 반시계 방향 $90^\circ$ 회전이라면 $m = 4$입니다.

입력은 두 줄로 이루어집니다.

첫 번째 줄에는 정수 $n$이 주어집니다 ($2 \le n \le 1024$, $n$은 짝수). 이미지는 $n \times n$ 픽셀 행렬 $(a_{i,j})$로 저장되며, $i$는 행 번호, $j$는 열 번호입니다. 왼쪽 위 픽셀의 위치는 행 $0$, 열 $0$입니다.

두 번째 줄에는 공백으로 구분된, 비어 있지 않은 최대 $32$개의 단어 목록이 주어집니다. 유효한 단어는 키워드 id, rot, sym, bhsym, bvsym, div, mix 중 하나이며, 뒤에 -가 붙을 수 있습니다. 각 키워드 key는 (아래 그림 1에서 정의된) 기본 변환을 나타내고, key-는 key의 역변환을 나타냅니다. 예를 들어 rot-는 반시계 방향 $90^\circ$ 회전의 역변환, 즉 시계 방향 $90^\circ$ 회전입니다.

목록 $k_1, k_2, \ldots, k_p$는 합성 변환 $\varphi = k_1 \circ k_2 \circ \cdots \circ k_p$를 나타냅니다. 즉, $k_p$를 가장 먼저 적용하고 $k_1$을 가장 나중에 적용합니다. 예를 들어 bvsym rot-는 먼저 시계 방향 $90^\circ$ 회전을 수행한 뒤, 이미지의 아래쪽 절반에 대해 상하 대칭을 적용합니다.

각 기본 변환은 이미지 $(a_{i,j})$를 다음과 같이 이미지 $(b_{i,j})$로 바꿉니다.

변환	그림
id — 항등변환. 아무것도 바뀌지 않습니다: $b_{i,j} = a_{i,j}$.
rot — 반시계 방향 $90^\circ$ 회전: $b_{i,j} = a_{j,\; n-1-i}$.
sym — 좌우 대칭: $b_{i,j} = a_{i,\; n-1-j}$.
bhsym — 아래쪽 절반에만 적용하는 좌우 대칭: $i \ge n/2$이면 $b_{i,j} = a_{i,\; n-1-j}$, 그렇지 않으면 $b_{i,j} = a_{i,j}$.
bvsym — 아래쪽 절반에만 적용하는 상하 대칭: $i \ge n/2$이면 $b_{i,j} = a_{\,3n/2 - 1 - i,\; j}$, 그렇지 않으면 $b_{i,j} = a_{i,j}$.
div — 나누기. 행 $0, 2, \ldots, n-2$는 행 $0, 1, \ldots, n/2 - 1$이 되고, 행 $1, 3, \ldots, n-1$은 행 $n/2, n/2 + 1, \ldots, n-1$이 됩니다.
mix — 행 섞기. 행 $2k$와 $2k+1$을 번갈아 끼워 넣습니다. 새 이미지의 행 $2k$는 $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}$이고, 새 이미지의 행 $2k+1$은 $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}$입니다.

그림 1: 각 변환이 이미지 $(a_{i,j})$를 이미지 $(b_{i,j})$로 바꾸는 방식.

$\varphi^m$이 항등변환이 되는 가장 작은 정수 $m$ ($m > 0$)을 한 줄에 출력합니다. 모든 입력에 대해 $m < 2^{31}$이라고 가정해도 됩니다.