DNA Sequence Transformation

Grace is a biologist at a bioinformatics company in Singapore. Part of her job is to analyze DNA sequences of organisms. In this problem, a DNA sequence is a string consisting of characters A, T, and C (note that the character G is not present).

A modification is defined as swapping the characters at two positions in the sequence. For example, by swapping the bold characters in ACTA (swapping the first bold C and the second bold A), one modification can transform it into AATC.

The modification distance between two sequences is the minimum number of modifications (swaps) required to transform one sequence into the other. If it is impossible to do so using modifications, the modification distance is defined to be \(-1\).

Grace is analyzing two DNA sequences \(a\) and \(b\), each of length \(n\) with indices from \(0\) to \(n-1\). Your task is to answer \(q\) queries. Each query is of the form: What is the modification distance between the substrings \(a[x \ldots y]\) and \(b[x \ldots y]\)? Here, for a DNA sequence \(s\), the substring \(s[x \ldots y]\) is defined as the contiguous sequence of characters from index \(x\) to \(y\) (both inclusive).

How to Determine the Modification Distance:

For a given query, let \(s = a[x \ldots y]\) and \(t = b[x \ldots y]\) (of length \(L = y - x + 1\)). First, note that it is possible to transform \(s\) into \(t\) by swaps if and only if \(s\) and \(t\) have the same multiset of characters (i.e. the same count for each of \(A\), \(T\), and \(C\)). If they do not, the answer is \(-1\).

If the multisets match, we now consider the positions where \(s\) and \(t\) differ. For every index \(i\) where \(s[i] \neq t[i]\), denote the ordered pair \((s[i], t[i])\). There are 6 possible mismatch pairs (since the letters are chosen from \(\{A,T,C\}\)): \((A,T)\), \((A,C)\), \((T,A)\), \((T,C)\), \((C,A)\), and \((C,T)\).

The key observation is that a single swap can simultaneously fix two mismatched positions if the mismatch pairs are complementary; that is, if for some indices \(i\) and \(j\) we have \( (s[i], t[i]) = (x, y) \) and \( (s[j], t[j]) = (y, x) \). In this case, one swap will fix both.

Let the counts for the mismatch pairs be:

[ \begin{aligned} cnt(A,T), \quad cnt(A,C), \quad cnt(T,A), \quad cnt(T,C), \quad cnt(C,A), \quad cnt(C,T). \end{aligned} ]

Then the number of "direct swaps" available is:

[ \text{direct} = \min(cnt(A,T),cnt(T,A)) + \min(cnt(A,C),cnt(C,A)) + \min(cnt(T,C),cnt(C,T)). ]

</p>

After these direct swaps, let \(R\) be the remaining number of mismatches. These remaining mismatches will always form cycles of length 3 (a 3-cycle) and each such cycle requires 2 swaps to fix. Hence, if \(R\) is the number of mismatches left, the additional swaps required is \(2\times\frac{R}{3}\) (note that \(R\) will be a multiple of 3 when the overall frequencies match).

Thus, if the transformation is possible, the modification distance is given by:

[ \text{answer} = \text{direct} + 2 \times \left(\frac{R}{3}\right). ]

</p>

Your task is to process \(q\) queries on the sequences.

inputFormat

The input begins with a line containing two integers \(n\) and \(q\) \((1 \leq n, q \leq 10^5)\), the length of the DNA sequences and the number of queries, respectively.

The next line contains the DNA sequence \(a\), a string of length \(n\) consisting of the characters A, T, and C.

The following line contains the DNA sequence \(b\) in the same format.

Each of the next \(q\) lines contains two integers \(x\) and \(y\) \((0 \le x \le y \le n-1)\), representing a query asking for the modification distance between the substrings \(a[x \ldots y]\) and \(b[x \ldots y]\).

outputFormat

For each query, output a single line with one integer: the modification distance between \(a[x \ldots y]\) and \(b[x \ldots y]\), or \(-1\) if it is impossible to transform one substring into the other.

sample

4 3
ACTA
AATC
0 3
1 2
0 1

1
-1
0

</p>