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

题目描述

江桥 给定一条数轴上的一条道路，道路被划分为 $n$ 个位置，编号从 $1$ 到 $n$。每个位置要么为空地（使用 $\texttt{'.'}$ 表示），要么为障碍点（使用 $\texttt{'\#'}$ 表示）。空地可自由通行，障碍不可通行。

对于一次从 $x$ 到 $y$ 的移动，江桥 可以预先选择一个整数 $k\ (k\ge 0)$，并在路径区间 $\left[\min(x,y),\max(x,y)\right]$ 上指定一个长度为 $k$ 的连续子区间。在该子区间内，他可以无视障碍，将其视为空地；区间外只能在空地上行走。

同时，江桥还可以额外再用 $1$ 次穿墙魔法，该魔法可以允许他再穿过一个障碍点。

求使得 江桥 能够从 $x$ 到 $y$ 的最小整数 $k$。

输入格式

第一行输入两个整数 $n,q$，分别表示道路长度和查询次数。 第二行输入一个长度为 $n$，仅由字符 $\texttt{'.'}$ 和 $\texttt{'\#'}$ 构成的字符串 $s$，表示道路每个位置的初始情况。 此后 $q$ 行，第 $i$ 行输入两个整数 $x_i,y_i$，表示第 $i$ 次询问。

输出格式

对于每一次询问，新起一行输出一个整数，表示使得 江桥 能够从 $x$ 到 $y$ 的最小整数 $k$。

6 2
.###..
1 6
5 6

2
0

样例解释

对于第一次询问，使得 $[2,3]$ 区间内的障碍点变为空地，然后再使用穿墙穿过 $[4,4]$，能使得江桥 从 $1$ 到 $6$，除此之外，江桥还可以选择使 $[3,4]$ 区间内的障碍点变为空地，然后再使用穿墙穿过 $[2,2]$，两种方式的答案均为 $2$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1、4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,q \leq 3 \times 10^5,1 \leq x_i,y_i \leq n,s_i \in \{'.','\#' \}$。