DNA 돌연변이

그레이스는 생물학자로 싱가폴에 있는 바이오인포매틱스 회사를 다니고 있다. 그녀가 하는 일 중에는 다양한 생물체의 DNA 서열을 분석하는 일도 있다. DNA 서열이란 A, T, C 세 가지 문자로 구성된 문자열로 정의된다. 주의할 점은, 본 문제에서 DNA 서열은 문자 G를 포함하지 않는다.

DNA 서열의 두 원소가 서로 교환되는 연산을 돌연변이 연산이라고 정의하자. 예를 들어, 다음 서열에서 강조된 A와 C를 서로 교환하는 한 번의 돌연변이 연산을 통해 ACTA를 AATC로 변환할 수 있다.

두 서열 사이의 돌연변이 거리는 하나의 서열을 다른 서열로 변환하는 데 필요한 돌연변이 연산의 최소 횟수로 정의되며, 만약 하나의 서열을 다른 서열로 돌연변이 연산으로 변환할 수 없는 경우에는 $-1$로 정의된다.

그레이스는 두 DNA 서열 $a$와 $b$를 분석하고 있다. $a$와 $b$는 둘 다 $n$개의 원소로 구성되어 있고 각 원소는 $0$부터 $n - 1$까지 번호가 붙어 있다. 당신이 해야 할 일은 그레이스가 $q$개의 다음과 같은 질문에 답하도록 돕는 것이다: 부분 문자열 $a[x..y]$와 부분 문자열 $b[x..y]$ 사이의 돌연변이 거리가 얼마인가? 여기에서, DNA 서열 $s$의 부분 문자열 $s[x..y]$란 $x$번부터 $y$번까지 $s$의 연속된 문자들의 서열로 정의된다. 즉, $s[x..y]$는 서열 $s[x]s[x + 1]\dots s[y]$이다.

구현 세부사항

다음 함수들을 구현해야 한다.

void init(string a, string b)

• a, b: 길이 $n$인 문자열로, 분석해야 할 두 DNA 서열을 의미한다.
• 이 함수는 get_distance를 호출하기 전에 정확하게 한 번 호출된다.

int get_distance(int x, int y)

• x, y: 분석해야 할 부분 문자열의 시작과 끝 번호.
• 이 함수는 부분 문자열 $a[x..y]$와 $b[x..y]$ 사이의 돌연변이 거리를 리턴해야 한다.
• 이 함수는 정확하게 $q$번 호출된다.

예제

다음 호출을 생각해 보자:

init("ATACAT", "ACTATA")

우선 그레이더가 다음을 호출하는 경우를 보자.

get_distance(1, 3)

이 호출은 $a[1..3]$과 $b[1..3]$, 즉 TAC와 CTA 사이의 돌연변이 거리를 리턴해야 한다. TAC는 두 번의 돌연변이 연산을 통해 CTA로 변환될 수 있다: $\mathtt{TAC} \rightarrow \mathtt{CAT}$, 그 후 $\mathtt{CAT} \rightarrow \mathtt{CTA}$. 두 번보다 적은 횟수의 돌연변이 연산으로 변환하는 것은 불가능하다.

따라서 이 호출은 $2$를 리턴해야 한다.

다음, 그레이더가 다음을 호출하는 경우를 보자.

get_distance(4, 5)

이 호출은 AT와 TA 사이의 돌연변이 거리를 리턴해야 한다. AT는 한 번의 돌연변이 연산을 통해 TA로 변환될 수 있고, 분명히 최소 한 번의 돌연변이 연산이 필요하다.

따라서 이 호출은 $1$을 리턴해야 한다.

마지막으로, 그레이더가 다음을 호출하는 경우를 보자.

get_distance(3, 5)

어떤 돌연변이 연산들을 이용하더라도 서열 CAT를 ATA로 변환할 수 있는 방법이 없으므로, 이 호출은 $-1$을 리턴해야 한다.

제약 조건

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

서브태스크

1. (21점) $y - x \le 2$
2. (22점) $q \le 500$, $y - x \le 1000$, $a$와 $b$의 각 문자는 A 또는 T이다.
3. (13점) $a$와 $b$의 각 문자는 A 또는 T이다.
4. (28점) $q \le 500$, $y - x \le 1000$
5. (16점) 추가적인 제약 조건은 없다.

line 1: n q
line 2: a
line 3: b
line 4 + i (0 ≤ i ≤ q - 1): x y (i번째 get_distance 호출을 위한 x와 y임)

샘플 그레이더는 다음 형식으로 답을 출력한다:

line 1 + i (0 ≤ i ≤ q - 1): i번째 get_distance 호출의 리턴 값

샘플 그레이더는 다음 형식으로 입력을 읽는다: