Mutating DNA

Grace는 싱가포르의 생물정보학 회사에서 일하는 생물학자다. 그녀는 업무의 일환으로 여러 생물의 DNA 서열을 분석한다. DNA 서열이란 문자 "A", "T", "C"로 이루어진 문자열이다. 이 문제에서 DNA 서열에는 문자 "G"가 들어 있지 않다.

변이란 DNA 서열의 두 원소를 교환하는 연산이다. 예를 들어 한 번의 변이로 "ACTA"의 강조된 문자 "A"와 "C"를 교환해 "AATC"로 바꿀 수 있다.

두 서열 사이의 변이 거리란 한 서열을 다른 서열로 바꾸는 데 필요한 변이의 최소 횟수이고, 변이만으로 한 서열을 다른 서열로 바꿀 수 없으면 $-1$이다.

Grace는 $n$개의 원소로 이루어지고 인덱스가 $0$부터 $n - 1$까지인 두 DNA 서열 $a$와 $b$를 분석한다. 당신은 부분 문자열 $a[x..y]$와 부분 문자열 $b[x..y]$ 사이의 변이 거리는 얼마인지 묻는 $q$개의 질문에 Grace가 답하도록 도와야 한다. DNA 서열 $s$의 부분 문자열 $s[x..y]$란 인덱스 $x$부터 $y$까지를 포함하는 $s$의 연속한 문자들로 이루어진 서열이다. 다시 말해 $s[x..y]$는 서열 $s[x]s[x + 1] \dots s[y]$이다.

• $1 \le n, q \le 100\,000$
• $0 \le x \le y \le n - 1$
• $a$와 $b$의 각 문자는 "A", "T", "C" 중 하나이다.