A君は人気のゲーム「ダンシング迷路」に没頭している。このゲームの迷路は、上から$i$行目、左から$j$列目の部屋の番号を$(i, j)$とする$H\times W$個の正方形の部屋を、縦と横にそれぞれ$H$行と$W$列に並べた長方形の領域である。
プレイヤーの目的は、迷路の入口がある部屋$(1,1)$から出口のある部屋$(H,W)$まで、最少の移動回数で移動することである。入口から出口まで移動する間、プレイヤーは一定の間隔で手拍子を打ち続けなければならない。ゲームは、プレイヤーが手拍子で刻む拍にしたがって進行する。
縦または横に隣り合う部屋の間は扉で仕切られている。ふだん扉は閉じられているが、最初の３拍のどれかの拍で開き、以後３拍ごとに開く。つまり、最初の３拍のうち$b$拍目($b=1, 2,3$)で開く扉は$b+3n$拍目だけで開く($n\geq0$)。最初の３拍のうちどの拍で開くかは、扉によって様々である。たとえば、最初の３拍のうち２拍目で開く扉は、その後５拍目、８拍目、…で開く。扉は手拍子の瞬間に開き、プレイヤーはその瞬間に開いている扉を通って、隣り合う部屋へ瞬時に移動できる。
プレイヤーは１拍ごとに移動しなければならない。このとき、１つの拍で移動できるのは一部屋だけである。移動できなければ、そこでゲームオーバーとなるため、プレイヤーは出口にはたどり着けない。移動を続けることができても、迷路によっては永久に出口にたどり着けない場合もある。
迷路の大きさと、隣り合う部屋との間の扉が開く拍の情報が与えられる。入口の部屋から出口の部屋へ移動するための最少の移動回数を求めよ。ただし、最初の拍は1とする。
入力は以下の形式で与えられる。
$H$ $W$ $row_1$ $row_2$ : $row_H$ $col_1$ $col_2$ : $col_W$
1行目に、迷路の縦方向の部屋の数$H$ ($2 \leq H \leq 100$)と横方向の部屋の数$W$ ($2 \leq W \leq 100$)が与えられる。続く$H$行に、$i$行目に並ぶ部屋の間の扉がいつ開くかを表す情報$row_i$が以下の形式で与えられる。
$d_{i,1}$ $d_{i,2}$ ... $d_{i,W-1}$
$d_{i,j}$ (1,2または3)は、$i$行目の部屋の並びで、横方向に$j$番目と$j+1$番目の間にある扉が最初の３拍のうちどの拍で開くかを表す整数である。
続く$W$行に、$j$列目に並ぶ部屋の間の扉がいつ開くかを表す情報$col_j$が以下の形式で与えられる。
$f_{1,j}$ $f_{2,j}$ ... $f_{H-1,j}$
$f_{i,j}$(1,2,または3)は、$j$列目の部屋の並びで、縦方向に$i$番目と$i+1$番目の間にある扉が最初の３拍のうちどの拍で開くかを表す整数である。
出口に移動できる場合は最少の移動回数を1行に出力する。どのように移動しても出口にたどり着けない場合は「-1」を出力する。
2 3 3 1 2 3 1 2 1
3
2 3 3 1 1 3 1 2 1
-1