R2公司在2D游戏领域的最后一个产品是一种在2×n迷宫中搜索最短路径的革命性新算法。
想象一个迷宫,看起来像一个 2 × n 矩形,分为单位正方形。每个单位方块要么是一个空单元格,要么是一个障碍物。在一个单位时间内,一个人可以从迷宫的一个空单元格移动到任何一侧相邻的空单元格。最短路径问题表述如下。给定两个自由迷宫单元,您需要确定从一个单元到达另一个单元所需的最短时间。
不幸的是,所开发的算法仅适用于寻找最短路径的一个请求,实际上此类请求经常发生。作为 R2 首席程序员,您受委托优化算法以找到最短路径。编写一个程序,该程序将有效地响应多个请求,以在 2 × n 迷宫中找到最短路径。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 2·105; 1 ≤ m ≤ 2·105) — 迷宫的宽度和查询的数量。接下来的两行包含迷宫。每行包含 n 个字符,每个字符等于“.” (空单元格)或“X”(障碍物)。
接下来的 m 行中的每一行都包含两个整数 vi 和 ui (1 ≤ vi, ui ≤ 2n) — 第 i 个请求的描述。数字vi、ui表示需要打印从迷宫编号vi的单元格到编号ui的单元格的最短路径的值。我们假设迷宫第一行的单元格从左到右编号为1到n,第二行的单元格从左到右编号为n+1到2n。保证两个给定的单元格都是空的。
输出
打印 m 行。在第 i 行中,打印第 i 个请求的答案 - 如果我们无法从第一个单元格到达第二个单元格,则打印最短路径的大小或 -1。
示例
输入 #1
4 7 .X.. ...X 5 1 1 3 7 7 1 4 6 1 4 7 5 7
输出 #1
1 4 0 5 2 2 2
输入 #2
10 3 X...X..X.. ..X...X..X 11 7 7 18 18 10
输出 #2
9 -1 3