Mê cung 2D

Một mê cung có dạng hình chữ nhật kích thước $2\times n$, chia thành các ô vuông đơn vị. Mỗi ô hoặc là ô trống, hoặc là ô có vật cản.

Trong một đơn vị thời gian, một người có thể di chuyển từ một ô trống sang một ô trống kề cạnh với nó.

Các ô ở hàng thứ nhất được đánh số từ $1$ đến $n$ theo thứ tự từ trái sang phải, các ô ở hàng thứ hai được đánh số từ $n+1$ đến $2n$ cũng theo thứ tự từ trái sang phải.

Cho $m$ truy vấn, mỗi truy vấn gồm hai ô trống $v$ và $u$. Với mỗi truy vấn, hãy tìm thời gian ít nhất để đi từ ô $v$ đến ô $u$, hoặc cho biết không thể đi được.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$: chiều rộng của mê cung và số truy vấn.
• Hai dòng tiếp theo mô tả mê cung, mỗi dòng gồm $n$ ký tự, mỗi ký tự là . (ô trống) hoặc X (vật cản).
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $v_i$ và $u_i$ mô tả truy vấn thứ $i$. Đảm bảo cả hai ô này đều là ô trống.

Dữ liệu ra

In ra $m$ dòng. Dòng thứ $i$ chứa độ dài đường đi ngắn nhất từ ô $v_i$ đến ô $u_i$, hoặc $-1$ nếu không thể đi từ ô này tới ô kia.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le m\le 2·{10}^5$
• $1\le v_i,u_i\le 2n$

Ví dụ