P10273 The Greatest Entertainment Above All

> Glitter, black holes, the star that everyone watches. > > In the most beautiful dream of the most beautiful land. > > Her hair is more expensive than gold leaf, her lipprints can be worth bundles of cash. > > But her heart, her heart, her heart, > > Is not worth a single gold coin, not worth a single gold coin, not worth a glance.

You are given a string $S$ of length $n$ consisting of lowercase letters, and a binary string $b$ of length $n$. $b_i=1$ means that $S_i$ can be modified. You are given $m$ substrings $S_{[l,r]}$. A substring $str$ is defined to be **non-partially-ordered** if and only if it is possible to modify at most one position of $S$ so that, among the $m$ substrings, all substrings that were originally $< str$ become $\ge str$. Formally, a pair $(l_i,r_i)$ is **non-partially-ordered** if and only if there exists a string $T$ (obtained from $S$ by modifying at most one character) such that $\forall\,1 \le j \le m,[S_{[l_j,r_j]}

The first line contains two integers $n,m$. The second line contains a string $S$. The third line contains a binary string $b$. The next $m$ lines each contain a pair $(l_i,r_i)$.

Output a binary string $ans$ of length $m$. $ans_i=1$ means that $(l_i,r_i)$ is `non-partially-ordered`, and $ans_i=0$ means it is not.

### Explanation of Sample 1 For convenience, assume the character smaller than `a` is `#`, and the character larger than `z` is `*`. - $(1,5):$ No matter how you modify, it always holds that $S_{[1,3]}