Problem

Description

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 × nmaze.

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.

Input

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 ≤ 2n) — 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 2n from left to right. It is guaranteed that both given cells are empty.

Output

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.

Sample Input

Sample Output

HINT

无

Solution

Analysis

直接进行查询操作

Attention

无

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
const int N=200001;
const int inf=0x3f3f3f3f;
int n,m;
char a[3][N];
#define ls (o<<1)
#define rs ((o<<1)|1)
struct node{
    int d1,d2,d3,d4;
}t[N<<2];
//d1 左上->右上
//d2 左上->右下
//d3 左下->右上
//d4 左下->右下
il node merge(node A,node B){
    node res;
    res.d1=min(inf,min(A.d1+B.d1,A.d2+B.d3)+1);
    res.d2=min(inf,min(A.d1+B.d2,A.d2+B.d4)+1);
    res.d3=min(inf,min(A.d3+B.d1,A.d4+B.d3)+1);
    res.d4=min(inf,min(A.d4+B.d4,A.d3+B.d2)+1);
    return res;    
}
il node query(int o,int l,int r,int L,int R){
    if(l==L && r==R)
        return t[o];
    int mid=(L+R)>>1;
    if(r<=mid) return query(ls,l,r,L,mid);
    if(l>mid) return query(rs,l,r,mid+1,R);
    return merge(query(ls,l,mid,L,mid),query(rs,mid+1,r,mid+1,R));
}
il void build(int o,int l,int r){
    if(l==r){
        t[o].d1=t[o].d2=t[o].d3=t[o].d4=inf;
        if(a[1][l]=='.') t[o].d1=0;
        if(a[2][l]=='.') t[o].d4=0;
        if(a[1][l]=='.' && a[2][l]=='.') t[o].d2=t[o].d3=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    t[o]=merge(t[ls],t[rs]);
}
int main(){
    n=read();m=read();
    rep(i,1,2) scanf("%s",a[i]+1);
    build(1,1,n);
    while(m--){
        int x=read(),y=read();
        bool se1=0,se2=0;
        if(x>n) x-=n,se1=1;
        if(y>n) y-=n,se2=1;
        if(x>y){
            swap(x,y);
            swap(se1,se2);
        }
        node ans=query(1,x,y,1,n);
        if(se1){
            if(se2)
                printf("%d\n",(ans.d4==inf)?-1:ans.d4);
            else
                printf("%d\n",(ans.d3==inf)?-1:ans.d3);
        }else{
            if(se2)
                printf("%d\n",(ans.d2==inf)?-1:ans.d2);
            else
                printf("%d\n",(ans.d1==inf)?-1:ans.d1);
        }
    }
    return 0;
}

[CF413E] Maze 2D