Mutating DNA

Grace is a biologist working at a bioinformatics firm in Singapore. As part of her job, she analyses the DNA sequences of various organisms. A DNA sequence is a string consisting of the characters "A", "T", and "C". In this task, DNA sequences do not contain the character "G".

A mutation is an operation on a DNA sequence that swaps two elements of the sequence. For example, a single mutation can turn "ACTA" into "AATC" by swapping the highlighted characters "A" and "C".

The mutation distance between two sequences is the minimum number of mutations needed to turn one sequence into the other, or $-1$ if one sequence cannot be turned into the other using mutations.

Grace is analysing two DNA sequences $a$ and $b$, both with $n$ elements indexed from $0$ to $n - 1$. Your task is to help Grace answer $q$ questions of the form: what is the mutation distance between the substring $a[x..y]$ and the substring $b[x..y]$? Here a substring $s[x..y]$ of a DNA sequence $s$ is a sequence of consecutive characters of $s$ whose indices run from $x$ to $y$ inclusive. In other words, $s[x..y]$ is the sequence $s[x]s[x + 1] \dots s[y]$.

• $1 \le n, q \le 100\,000$
• $0 \le x \le y \le n - 1$
• Each character of $a$ and $b$ is one of "A", "T", and "C".