移动

题号：NC296222
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Bingbong 给定一条数轴上的一条道路，道路被划分为 $n$ 个位置，编号从 $1$ 到 $n$ 。每个位置要么为空地（使用 $\texttt{`.'}$ 表示），要么为障碍点（使用 $\texttt{`\#'}$ 表示）。空地可自由通行，障碍不可通行。
$\hspace{15pt}$ 对于一次从 $x$ 到 $y$ 的移动，Bingbong 可以预先选择一个整数 $k\ (k\ge 0)$ ，并在路径区间 $\left[\min(x,y),\max(x,y)\right]$ 上指定一个长度为 $k$ 的连续子区间。在该子区间内，他可以无视障碍，将其视为空地；区间外只能在空地上行走。
$\hspace{15pt}$ 求使得 Bingbong 能够从 $x$ 到 $y$ 的最小整数 $k$ 。

输入描述:

第一行输入两个整数 ，分别表示道路长度和查询次数。
第二行输入一个长度为 ，仅由字符  和  构成的字符串 ，表示道路每个位置的初始情况。
此后  行，第  行输入两个整数 ，表示第  次询问，保证 。

输出描述:

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

示例1

输入

复制

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

输出

复制

3
0

说明

对于第一次询问，必须要使得  区间内的障碍点变为空地，才能使得 Bingbong 从  到 。
对于第二次询问， 到  之间没有障碍点，所以 。

示例2

输入

复制

输出

复制

1
1
0

备注:

本题数据量较大，我们建议您选取较快的读入方式。