SOLVE
LATER
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}\).
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\).
Challenge Name
HackerEarth Collegiate Cup - First Elimination
HackerEarth Collegiate Cup - First Elimination