该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

毕业季打桌面游戏打疯了的小明终于做梦梦到了自己来到了桌面游戏的世界，这是一个平面王国，这个平面王国可以描述成一个 $2\times N$ 的矩阵，矩阵中的每一个方格是一个城市，编号为 $1,2,\dots,2N$，城市分布如下。有些城市是无法到达的。一个城市可以到达与之曼哈顿距离为 $1$ 的城市。

• 所谓「曼哈顿距离」，就是两点之间横坐标差的绝对值+纵坐标差的绝对值。形式化的说，假设两点坐标为 $(x_1,y_1)$，$(x_2,y_2)$，那么这两点之间的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$。

【城市编号分布示意图如下】

小明到了这个桌面王国后正在规划旅行，他想知道如果在从编号为 $L$ 的城市出发到编号为 $R$ 的城市的最少需要经过多少城市，这样的询问有 $M$ 个。

输入格式

第一行输入两个正整数 $N$ 和 $M$，$N$ 表示城市矩阵的列，$M$ 表示询问的数量。

接下来两行，每行是一个长度为 $N$ 的字符串，表示对应的城市能否经过。 若为 X，表示不能经过，若为 P，表示可以经过。

接下来有 $M$ 行，每行两个整数 $L,R$，描述一个询问。

输出格式

对于每个询问输出一行，$L$ 编号城市到 $R$ 编号城市需要经过的最少城市个数(注意：不包括起点，但包括终点)，若无法到达则输出 $-1$。

3 4 
XPX
PPP
1 4
4 2
6 5 
6 4

-1
2
1
2

提示

【样例解释】

对于第一个询问，要从 $1$ 走到 $4$，编号 $1$ 城市为 X，不能经过，所以输出 $-1$。

对于第二个询问，要从 $4$ 走到 $2$，最少经过城市的走法为 $4 \rightarrow 5 \rightarrow 2$，经过的城市为 $5,2$，不包括起点，但包括重点，所以输出 $2$。

对于第三个询问，要从 $6$ 走到 $5$，最少经过城市的走法为 $6 \rightarrow 5$，输出 $1$。

对于第四个询问，要从 $6$ 走到 $4$，最少经过城市的走法为 $6 \rightarrow 5 \rightarrow 4$，输出 $2$。

【数据范围】

对于 $30\%$ 数据,，$n,m \le 10^3$；

对于 $100\%$ 数据，$n,m \le 2 \times 10^5$。