AT_abc429_f [ABC429F] Shortest Path Query

$ 3 $ 行 $ N $ 列のグリッドが与えられます。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と表します。マス $ (i,j) $ には $ S_{i,j} $ が `#` ならば壁マスで、 `.` ならば空きマスであり通行可能です。 $ Q $ 個のクエリが与えられるので、順に処理してください。 各クエリでは整数 $ r,c $ が与えられるので、マス $ (r,c) $ の状態を反転させてください。つまり、マス $ (r,c) $ が壁マスならば空きマスにし、空きマスならば壁マスにしてください。その後、以下の問題の答えを出力してください。 > マス $ (1,1) $ から上下左右に隣接する空きマスに移動する操作を繰り返してマス $ (3,N) $ に移動することを考えます。このとき、マス $ (3,N) $ に到達できるか判定し、到達できる場合は操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_{1,1}S_{1,2}\ldots S_{1,N} $ $ S_{2,1}S_{2,2}\ldots S_{2,N} $ $ S_{3,1}S_{3,2}\ldots S_{3,N} $ $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ 各クエリは以下の形式で与えられる。 > $ r $ $ c $

$ Q $ 行出力せよ。 $ i $ 行目 $ (1\le i\le Q) $ には、 $ i $ 番目のクエリにおいてマス $ (1,1) $ からマス $ (3,N) $ に到達不可能ならば `-1` を、到達可能ならば操作回数の最小値を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のクエリではマス $ (1,2) $ の状態を反転させます。その結果、各マスの状態は以下のようになります。 ``` ..... .#.#. ...#. ``` このとき、マス $ (1,1) $ から順にマス $ (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) $ と移動することで $ 6 $ 回の操作でマス $ (3,5) $ に到達することができます。 $ 2 $ つ目のクエリではマス $ (1,2) $ の状態を反転させます。その結果、各マスの状態は以下のようになります。 ``` .#... .#.#. ...#. ``` このとき、マス $ (1,1) $ から順にマス $ (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) $ と移動することで $ 10 $ 回の操作でマス $ (3,5) $ に到達することができます。 $ 3 $ つ目のクエリではマス $ (2,3) $ の状態を反転させます。その結果、各マスの状態は以下のようになります。 ``` .#... .###. ...#. ``` このとき、どのように操作してもマス $ (1,1) $ からマス $ (3,5) $ に到達することはできません。 ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ S_{i,j} $ は `#` または `.` - $ S_{1,1}=S_{3,N}= $ `.` - $ 1\le Q\le 2\times 10^5 $ - $ 1\le r\le 3 $ - $ 1\le c\le N $ - $ (r,c) \neq (1,1),(3,N) $ - $ N,Q,r,c $ は整数