The Siruseri amusement park has a new attraction. It consists of a rectangular array of discs. Each disc is divided into four equal sectors and the four sectors are coloured with the colours Red, Blue, Green and Yellow (in some order). The ordering may be different in different discs. Here is a possible arrangment of the discs:

You start at the top left disc. Your task is to walk down to the bottom right disc. In each step, you can rotate the current disc by $90$ degrees in the clockwise direction or move to a neighbouring disc. However, you can move to a neighbouring disc only if adjacent sectors of these two discs have the same colour. For example, in the figure above, you can move from the disc at position ($1$, $1$) to either of its neighbours. However, from the disc at position ($1$, $2$) you can only move to the disc at position ($1$, $1$). If you wish to move from ($1$, $2$) to ($1$, $3$) then you would have to rotate this disc three times so that the colour (red) on the adjacent sectors are the same.
For each rotate move, a penalty point is added to the score. The aim is to reach the bottom right with as few penalty points as possible. For example, in the arrangement described in the above figure, the best possible score is $2$, corresponding to the following path: Move from ($1$, $1$) to ($2$, $1$). Move from ($2$, $1$) to ($2$, $2$). Rotate. Rotate. Move from ($2$, $2$) to ($2$, $3$). Move from ($2$, $3$) to ($1$, $3$). Move from ($1$, $3$) to ($1$, $4$). Finally, move from ($1$, $4$) to ($2$, $4$).
Your task is to determine the minimum number of penalty points required to go from the top left disc to the bottom right disc for the given arrangement of discs.

-----Input:-----
The first line contains two integers $M$ and $N$. $M$ is the number of rows and $N$ is the number of columns in the given arrangment. This is followed by $M \times N$ lines of input. Lines $2$ to $N+1$, describe the colours on the discs on the first row, Lines $N+2$ to $2 \cdot N+1$ describe the colours on discs in the second row and so on. Each of these lines contain a permutation of the set {R, G, B, Y} giving the colours in the top, right, bottom and left sectors in that order.

-----Output:-----
A single integer on a single line indicating the minimum number of penalty points required to go from the top left disc to the bottom right disc for the given arrangement of discs.

-----Constraints:-----
- In $80 \%$ of the input, $1 \leq M,N \leq 60$.
- In all the inputs $1 \leq M,N \leq 1000$.

-----Sample Input-----
2 4
G Y B R
B G R Y
G Y B R
G R B Y
B Y G R
G B R Y
B R G Y
B R G Y

-----Sample Output-----
2

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from bisect import insort\nclass disk:\n    def __init__(self):\n        self.U = ''\n        self.D = ''\n        self.L = ''\n        self.R = ''\n        \n        \nm, n = map(int,input().split())\nadj = [[] for _ in range(m*n)]\ngrid = [[disk() for _ in range(n)] for _ in range(m)]\nfor i in range(m):\n    for j in range(n):\n        grid[i][j].U,grid[i][j].R,grid[i][j].D,grid[i][j].L = input().split()\nfor i in range(m):\n\tfor j in range(n):\n\t\tif (j!=0):\n\n\t\t\tif (grid[i][j].R == grid[i][j-1].R):\n\t\t\t    dist = 2\n\t\t\tif (grid[i][j].U == grid[i][j-1].R): \n\t\t\t    dist = 3\n\t\t\tif (grid[i][j].L == grid[i][j-1].R): \n\t\t\t    dist = 0\n\t\t\tif (grid[i][j].D == grid[i][j-1].R): \n\t\t\t    dist = 1\n\t\t\tadj[i*n + j].append((dist, i*n + j - 1))\n\t\t\n\t\tif (j!=n-1):\n\n\t\t\tif (grid[i][j].R == grid[i][j+1].L): \n\t\t\t    dist = 0\n\t\t\tif (grid[i][j].U == grid[i][j+1].L): \n\t\t\t    dist = 1\n\t\t\tif (grid[i][j].L == grid[i][j+1].L): \n\t\t\t    dist = 2\n\t\t\tif (grid[i][j].D == grid[i][j+1].L): \n\t\t\t    dist = 3\n\t\t\tadj[i*n + j].append((dist, i*n + j + 1))\n\n\t\t\n\t\tif (i!=0):\n\n\t\t\tif (grid[i][j].R == grid[i-1][j].D):\n\t\t\t    dist = 3\n\t\t\tif (grid[i][j].U == grid[i-1][j].D):\n\t\t\t    dist = 0\n\t\t\tif (grid[i][j].L == grid[i-1][j].D):\n\t\t\t    dist = 1\n\t\t\tif (grid[i][j].D == grid[i-1][j].D):\n\t\t\t    dist = 2\n\t\t\tadj[i*n + j].append((dist, i*n + j - n))\n\n\t\t\n\t\tif (i!=m-1):\n\n\t\t\tif (grid[i][j].R == grid[i+1][j].U): \n\t\t\t    dist = 1\n\t\t\tif (grid[i][j].U == grid[i+1][j].U): \n\t\t\t    dist = 2\n\t\t\tif (grid[i][j].L == grid[i+1][j].U): \n\t\t\t    dist = 3\n\t\t\tif (grid[i][j].D == grid[i+1][j].U):\n\t\t\t    dist = 0\n\t\t\tadj[i*n + j].append((dist, i*n + j + n))\nq = []\nq.append((0,0))\ndists = [2147483647 for _ in range(m*n)]\nvisited = [False for _ in range(m*n)]\ndists[0] = 0\nwhile q:\n    cur = q[-1]\n    q.pop()\n    if visited[cur[1]] == False:\n        visited[cur[1]] = True\n        dists[cur[1]] = -1*cur[0]\n    for i in range(len(adj[cur[1]])):\n        to = adj[cur[1]][i][1]\n        dis = adj[cur[1]][i][0]\n        if (not visited[to] and dists[cur[1]] + dis < dists[to]):\n            insort(q,(-1*(dists[cur[1]] + dis),to))\nprint(dists[m*n - 1])"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18631