Non‐Partial Order Substrings

You are given a lowercase string S of length n and a binary string b of length n, where b_i=1 indicates that the character S_i is allowed to be modified. You are also given m queries, each query specifying a substring S[l,r] (1-indexed). A substring str (specified by an interval) is called non‐partial order if and only if there exists a string T (which is obtained from S by modifying at most one character at a position where b_i=1) such that for every one of the m given substrings S[l_j,r_j] that were originally less than str (in lexicographic order), the corresponding substring in T is not less than the substring of T from str.

In other words, let the original string be S and let T be obtained by changing at most one modifiable position of S. For a candidate query i with substring S[l_i,r_i], we require that for every query j (with substring S[l_j,r_j]) for which

[ S[l_j,r_j] < S[l_i,r_i], ]

it must hold that

[ T[l_j,r_j] \ge T[l_i,r_i]. ]

Here the comparisons are done in lexicographic order. Note that if T is identical to S (i.e. no modification is made) then the condition must hold for every such pair; otherwise, you may choose some modifiable position p (with b_p=1) and change S[p] to a new character (the new character may even be outside the range a–z) in order to "correct" the order. However, the modification affects every substring that covers the changed index.

Your task is to determine, for each of the m queries, whether the corresponding substring is non‐partial order or not.

Note: When comparing two substrings, the lexicographical order is defined in the usual way. Also, if one string is a prefix of the other, the shorter one is considered to be lexicographically smaller.

inputFormat

The first line contains two integers n and m (the length of S and the number of queries).

The second line contains the string S (of lowercase letters).

The third line contains the binary string b (of length n), where each character is either 0 or 1.

Each of the next m lines contains two integers l and r (1-indexed) representing a query for the substring S[l,r].

outputFormat

For each query, output a single line containing Yes if the queried substring is non‐partial order, or No otherwise.

sample

5 3
abcde
11111
1 3
2 5
1 5

Yes
Yes
Yes