题目背景

闪光，黑洞，万众瞩目之星。

美丽的国度之中最美丽的梦。

她的发丝比金箔更贵，她的唇印可抵成捆钞票。

而她的心呀，心呀，心呀，

不值一枚金币，不值一枚金币，不值一瞧。

题目描述

给出一个由小写字母组成、长度为 $n$ 的字符串 $S$ 和一个长度为 $n$ 的 $01$ 串 $b$，$b_i=1$ 表示 $S_i$ 是可修改的。

给出 $m$ 个子串 $S_{[l,r]}$，定义一个子串 $str$ 是非偏序的，当且仅当可以通过修改 $S$ 的至多一个位置，使得 $m$ 个子串中原先 $<str$ 的子串都 $\ge str$。

形式化地说，一个二元组 $(l_i,r_i)$ 是非偏序的，当且仅当存在一个字符串 $T$（由 $S$ 修改至多一个字符得到），使得 $\forall\,1 \le j \le m,[S_{[l_j,r_j]}<S_{[l_i,r_i]}]+[T_{[l_j,r_j]}<T_{[l_i,r_i]}]\not=2$。

询问哪些子串是非偏序的。

注意，修改后出现比 a 小或比 z 大的字符是允许的。

输入格式

第一行两个数 $n,m$。

第二行一个字符串 $S$。

第三行一个 $01$ 串 $b$。

接下来 $m$ 行，每行一个二元组 $(l_i,r_i)$。

输出格式

输出为一个长度为 $m$ 的 $01$ 串 $ans$。$ans_i=1$ 表示 $(l_i,r_i)$ 是 非偏序 的，$ans_i=0$ 表示不是。

10 5
abbaababaa
0111111111
1 5
7 10
1 3
3 7
4 8

01111

提示

样例一解释

为了方便表述，钦定比 a 小的字符为 #，比 z 大的字符为 *。

• $(1,5):$ 无论如何修改，恒有 $S_{[1,3]}<S_{[1,5]},T_{[1,3]}<T_{[1,5]}$。

• $(7,10):$ $T$ 可以为 abbcababaa。

• $(1,3):$ $T$ 可以为 a#baababaa。

• $(3,7):$ $T$ 可以为 ab#aababaa。

• $(4,8):$ $T$ 可以为 abbaababaa。

数据范围与约定

本题采用捆绑测试。

$\text{subtask1(10pt):}$ $1 \le n,m \le 100$。

$\text{subtask2(30pt):}$ $1 \le n,m \le 1000$。

$\text{subtask3(10pt):}$ $b_i=1$。

$\text{subtask4(50pt):}$ 无特殊限制。

对于所有数据，$1\le n,m \le 2\times 10^5,1 \le l_i \le r_i \le n$，输入均为整数和小写字母。