Tag(s):

## Algorithms, Binary Search, Hashing, Medium, String Algorithms, Suffix Arrays

Problem
Editorial
Analytics

For a given two strings $S$ and $T$, both of length $N$, the task is to answer $Q$ queries.

Let $S_i$ be the $i^{th}$ letter of $S$, so $S_1$ is the first letter of $S$. Moreover, let $S_{i, j}$ denote the substring of $S$ starting with $S_i$ and ending in $S_j$. $T_{i, j}$ is defined analogously. For example, if $S = abba$, then $S_{2,4} = bba$. Each given query consists of $5$ integers $K, a, b, c, d$. The answer to the query is $\texttt{YES}$ if and only if substring $S_{a, b}$ can be obtained from substring $T_{c, d}$ by using at most $K$ swaps adjacent letters of $T_{c,d}$. Otherwise the answer is $\texttt{NO}$. More formally, a single swap of adjacent letters in $T$ is replacing simultaneously $T_i$ with $T_j$ and $T_j$ with $T_i$ for $j = i + 1$, where $1 \leq i \leq |T| - 1$.

For example if $S = abbab$ and $T = ababa$, then $S_{1, 3} = abb$ can be obtained from $T_{2, 4} = bab$ using a single swap. Moreover, if $S = abcab$ and $T = abcab$, then $S_{1, 3} = abc$ can be obtained from $T_{3, 5} = cab$ using $2$ swaps (first we can swap $c$ with $a$ and then $c$ with $b$). Notice that this cannot be done using less than $2$ swaps.

Input Format:

In the first line there is a single string $S$. In the second line there is a single string $T$. In the third line, there is a single integer $Q$ denoting the number of queries to handle. Each of the following $Q$ lines corresponds to a single query. In the $i^{th}$ of them, there are $5$ space separated integers $K, a, b, c, d$ describing the $i^{th}$ query.

Constraints:

$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$1 \leq a \leq b \leq N$
$1 \leq c \leq d \leq N$
$0 \leq K \leq 2$
each letter of $S$ is either $a$, $b$ or $c$

Output Format:

Output exactly $Q$ lines. In the $i^{th}$ of them print $\texttt{YES}$ if the answer to the $i^{th}$ query is positive. Otherwise, print $\texttt{NO}$.

SAMPLE INPUT
babba
abbaa
3
1 2 3 3 4
1 2 4 2 4
2 2 4 2 4

SAMPLE OUTPUT
YES
NO
YES

Explanation

In the sample, for the input strings $S = babba$ and $T = abbaa$, there are $4$ queries to answer. In the first one, it is asked if $S_{2,3} = ab$ can be obtained from $T_{3,4} = ba$ using at most $1$ swap. It can be achieved by performing the only available swap, so the answer is $\texttt{YES}$. In the second query, $S_{2,4} = abb$, $T_{2, 4} = bba$ and only one swap can be used. Since any single swap doesn’t produce the desired result, the answer for this query is $\texttt{NO}$. In the third query, given substring are the same as in the second query, but $2$ swaps are allowed. The answer for this query is $\texttt{YES}$, because $S_{2,4} = abb$ can be obtained from $T_{2,4} = bba$ by first swapping $b$ with $a$ to get $bab$ and then by swapping first $b$ with $a$ to get $abb$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup - First Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Bit Manipulation
• Math > Number Theory
• Math > Counting
• Math > Basic Geometry