A93108.「雅礼集训 2017 Day7」事情的相似度

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

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

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

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

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

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

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

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

测试点	$ n = $	$ m = $
1 ~ 2	$ 100 $	$ 100 $
3 ~ 4	$ 300 $	$ 1000 $
5 ~ 6	$ 5000 $	$ 5000 $
7 ~ 10	$ 100000 $	$ 300 $
11 ~ 14	$ 50000 $	$ 50000 $
15 ~ 20	$ 100000 $	$ 100000 $