大娱乐至上

> 闪光，黑洞，万众瞩目之星。 > > 美丽的国度之中最美丽的梦。 > > 她的发丝比金箔更贵，她的唇印可抵成捆钞票。 > > 而她的心呀，心呀，心呀， > > 不值一枚金币，不值一枚金币，不值一瞧。

给出一个由小写字母组成、长度为 $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$，输入均为整数和小写字母。