Background

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.

Problem Description

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]}<S_{[l_i,r_i]}]+[T_{[l_j,r_j]}<T_{[l_i,r_i]}]\not=2$.

Determine which substrings are non-partially-ordered.

Note that after modification, characters smaller than a or larger than z are allowed.

Input Format

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 Format

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.

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

01111

Hint

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]}<S_{[1,5]},T_{[1,3]}<T_{[1,5]}$.

• $(7,10):$ $T$ can be abbcababaa.

• $(1,3):$ $T$ can be a#baababaa.

• $(3,7):$ $T$ can be ab#aababaa.

• $(4,8):$ $T$ can be abbaababaa.

Constraints and Notes

This problem uses bundled testdata.

$\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):}$ No special restrictions.

For all testdata, $1\le n,m \le 2\times 10^5,1 \le l_i \le r_i \le n$. All inputs are integers and lowercase letters.

Translated by ChatGPT 5