题目描述

人的一生不仅要靠自我奋斗，还要考虑到历史的行程。

历史的行程可以抽象成一个 01 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。

你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 11 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。

你发现，一件事情可以看成是这个 01 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。

两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。

现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？

输入格式

第一行两个整数 $ n $、$ m $，表示串长和询问个数。
第二行长度为 $ n $ 的 01 串，表示历史的行程。
接下来 $ m $ 行，每行两个正整数 $ l $、$ r $ 表示询问的区间，包括端点，保证 $ 1 \leq l < r \leq n $。

输出格式

输出 $ m $ 行，对每个询问输出一个整数表示最大的相似度。

样例

input

4 2
0101
1 3
2 4

output

1
2

数据范围与提示