C. Co-sortable Strings
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

Rami, Yessine and Oussama recently participated on a competitive programming contest. And after finishing it, they were tired. So, to have some fun, they decided to go to the café at $$$\text{16:00}.$$$

Usually, Oussama is the first one to come, and he will always wait for Rami and Yessine to come $$$15$$$ to $$$30$$$ minutes late. But this time, Rami and Yessine are at the café and Oussama did not come yet.

As this situation is a little bit strange, Yessine called Oussama to check where he is, and of course, Oussama told him that he is ready, but he is just checking why his greedy solution was not accepted in the contest, and once he knows what is wrong with it, he will come.

Now, Yessine knows very well that this may take some time, so he invented a little challenge with Rami that will kill their time:

  1. First of all, he created two strings $$$A$$$ and $$$B$$$ both of length $$$L$$$ and having only lowercase characters:
  2. Then, for two substring $$$A[l\dots r],B[l\dots r]$$$ of $$$A$$$ and $$$B$$$ respectively, he called them co-sortable if they can be simultaneously sorted using the following steps:
    • Choose $$$i\in\{l,\dots ,r\}$$$ and swap $$$A[i]$$$ and $$$B[i].$$$
    • Repeat the rule above as many times as you want.
  3. Now he asked Rami $$$Q$$$ questions of the same type. That is , the $$$i^\text{th}$$$ question takes two parameters $$$l_i \leq r_i$$$ and is of the form: Are the substrings $$$A[l_i\dots r_i]$$$ and $$$B[l_i\dots r_i]$$$ co-sortable?

Rami was overwhelmed by the number of such questions, so he asked you to help him answer the question so that Yessine won't win the challenge.

Input

1. The first line contains two integers $$$L,Q$$$ with $$$1\leq L\leq 10^5$$$ the length of the two strings, and $$$1\leq Q \leq 10^5$$$ the number of questions

2. The next two lines contain the lowercase alphabetic strings $$$A$$$ and $$$B$$$ respectively.

3. The next $$$Q$$$ lines contains each two integers, with the $$$i^\text{th}$$$ line having the parameters $$$1\leq l_i\leq r_i \leq L$$$

Output

$$$Q$$$ lines, with the $$$i^\text{th}$$$ line equal to $$$\texttt{YES}$$$ if the two substrings $$$A[l_i\dots r_i]$$$ and $$$B[l_i\dots r_i]$$$ are co-sortable. Else output $$$\texttt{NO}.$$$

Example
Input
3 3
cbc
adc
1 2
1 1
1 3
Output
YES
YES
NO
Note

For the first question, $$$A[1,2]=\text{cb}$$$ and $$$B[1,2]=\text{'ad'}.$$$ Initially they are not sorted, but by swapping $$$A[1]$$$ and $$$B[1]$$$ we will have $$$\text{'ab'}$$$ and $$$\text{'cd'}$$$ which are both sorted. So $$$A[1,2]$$$ and $$$B[1,2]$$$ are co-sortable.