AT_abc429_f [ABC429F] Shortest Path Query

You are given a grid with three rows and $ N $ columns. Denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left as cell $ (i,j) $ . Cell $ (i,j) $ is a wall cell if $ S_{i,j} $ is `#`, and an empty cell and passable if it is `.`. You are given $ Q $ queries, which you should process in order. Each query gives integers $ r $ and $ c $ , and you should flip the state of cell $ (r,c) $ . That is, if cell $ (r,c) $ is a wall cell, make it an empty cell, and if it is an empty cell, make it a wall cell. Then, output the answer to the following problem: > Consider moving from cell $ (1,1) $ to cell $ (3,N) $ by repeatedly moving to an empty cell adjacent up, down, left, or right. Determine whether cell $ (3,N) $ is reachable, and if reachable, find the minimum number of moves.

The input is given from Standard Input in the following format: > $ 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 $ Each query is given in the following format: > $ r $ $ c $

Print $ Q $ lines. On the $ i $ -th line $ (1\le i\le Q) $ , if cell $ (3,N) $ is unreachable from cell $ (1,1) $ in the $ i $ -th query, print `-1`; if reachable, print the minimum number of moves.

### Sample Explanation 1 In the first query, flip the state of cell $ (1,2) $ . As a result, the state of each cell becomes: ``` ..... .#.#. ...#. ``` At this time, by moving from cell $ (1,1) $ through cells $ (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) $ in order, you can reach cell $ (3,5) $ in six moves. In the second query, flip the state of cell $ (1,2) $ . As a result, the state of each cell becomes: ``` .#... .#.#. ...#. ``` At this time, by moving from cell $ (1,1) $ through cells $ (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) $ in order, you can reach cell $ (3,5) $ in ten moves. In the third query, flip the state of cell $ (2,3) $ . As a result, the state of each cell becomes: ``` .#... .###. ...#. ``` At this time, no matter how you move, you cannot reach cell $ (3,5) $ from cell $ (1,1) $ . ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ S_{i,j} $ is `#` or `.`. - $ 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 $ are integers.