CF413E.Maze 2D

The last product of the R2 company in the 2D games' field is a new revolutionary algorithm of searching for the shortest path in a 2 × n maze.

Imagine a maze that looks like a 2 × n rectangle, divided into unit squares. Each unit square is either an empty cell or an obstacle. In one unit of time, a person can move from an empty cell of the maze to any side-adjacent empty cell. The shortest path problem is formulated as follows. Given two free maze cells, you need to determine the minimum time required to go from one cell to the other.

Unfortunately, the developed algorithm works well for only one request for finding the shortest path, in practice such requests occur quite often. You, as the chief R2 programmer, are commissioned to optimize the algorithm to find the shortest path. Write a program that will effectively respond to multiple requests to find the shortest path in a 2 × n maze.

R2 公司在二维游戏领域的最新产品是一种用于在 $2 \times n$ 迷宫中搜索最短路径的全新革命性算法。

想象一个形如 $2 \times n$ 矩形的迷宫，它被划分为若干单位方格。每个单位方格要么是空单元格，要么是障碍物。在单位时间内，一个人可以从迷宫中的一个空单元格移动到任意一个与其共享一条边的相邻空单元格。最短路径问题定义如下：给定迷宫中两个空单元格，你需要确定从其中一个单元格到达另一个单元格所需的最少时间。

遗憾的是，该算法仅对单次最短路径查询效果良好；而实际应用中，此类查询却频繁发生。作为 R2 公司的首席程序员，你受命对该算法进行优化，以支持多次最短路径查询。请编写一个程序，能够高效地响应对 $2 \times n$ 迷宫的多次最短路径查询。

The first line contains two integers, n and m (1 ≤ n ≤ 2·105; 1 ≤ m ≤ 2·105) — the width of the maze and the number of queries, correspondingly. Next two lines contain the maze. Each line contains n characters, each character equals either '.' (empty cell), or 'X' (obstacle).

Each of the next m lines contains two integers v__i and u__i (1 ≤ v__i, u__i ≤ 2_n_) — the description of the i-th request. Numbers v__i, u__i mean that you need to print the value of the shortest path from the cell of the maze number v__i to the cell number u__i. We assume that the cells of the first line of the maze are numbered from 1 to n, from left to right, and the cells of the second line are numbered from n + 1 to 2_n_ from left to right. It is guaranteed that both given cells are empty.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq m \leq 2 \cdot 10^5$），分别表示迷宫的宽度和查询次数。接下来两行描述迷宫。每行包含 $n$ 个字符，每个字符为 '.'（空单元格）或 'X'（障碍物）。

接下来的 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq 2n$），表示第 $i$ 个查询。数值 $v_i$、$u_i$ 表示你需要输出从迷宫中编号为 $v_i$ 的单元格到编号为 $u_i$ 的单元格的最短路径长度。我们约定：迷宫第一行的单元格从左至右编号为 $1$ 到 $n$，第二行的单元格从左至右编号为 $n+1$ 到 $2n$。保证所给的两个单元格均为空。

Print m lines. In the i-th line print the answer to the i-th request — either the size of the shortest path or -1, if we can't reach the second cell from the first one.

输出 m 行。在第 i 行中输出第 i 个查询的答案——即最短路径的长度，若无法从第一个格子到达第二个格子，则输出 -1。