문제
석표는 유전자를 가지고 놀고 있다.
유전자는 A, T, C의 세 종류의 문자로 이루어진 문자열이다.
석표는 기계를 한 번 작동시켜서 유전자에서 원하는 두 글자의 위치를 바꿀 수 있다.
석표에게는 두 유전자 S, T를 가지고 있고 둘의 길이는 모두 N이다.
석표는 두 유전자에서 l번째 글자부터 r번째 글자까지를 잘라내어 가지고 논다. (가장 앞글자는 0번째)
석표는 S에서 잘라낸 유전자를 T에서 잘라낸 것과 같게 만들기 위해 최소 몇 번이나 기계를 써야할지 궁금해졌다.
호기심이 많은 석표는 이런 질문을 Q개의 l, r쌍에 대해 가지고 있다.
각각의 질문을 대답하는 프로그램을 만들어보자.
입력
다음의 형태로 입력이 주어진다.
N Q
S
T
l_1 r_1
...
l_Q r_Q
1 <= N, Q <= 100,000
0 <= l_i, r_i <= n-1
(l, r은 0-base)
출력
Q개의 질문에 대해 각 줄에 질문의 답을 출력하라.
유전자를 바꿀 수 없다면 -1을 출력하고, 있다면 최소 횟수를 출력하라.
예제
6 3
ATACAT
ACTATA
1 3
4 5
3 5
2
1
-1
출처
IOI 2021 day2
로그인해야 코드를 작성할 수 있어요.