Grace là một nhà sinh học làm việc tại một công ty tin sinh học ở Singapore. Trong công việc của mình, cô phân tích các chuỗi ADN của nhiều sinh vật khác nhau. Một chuỗi ADN được định nghĩa là một xâu gồm các ký tự A, T và C. Chú ý rằng trong bài này, các chuỗi ADN không chứa ký tự G.

Một phép đột biến là thao tác hoán đổi hai phần tử của một chuỗi ADN. Ví dụ, một phép đột biến có thể biến ACTA thành AATC bằng cách hoán đổi hai ký tự A và C được in đậm.

Khoảng cách đột biến giữa hai chuỗi là số phép đột biến ít nhất cần thực hiện để biến chuỗi này thành chuỗi kia, hoặc bằng \(-1\) nếu không thể biến chuỗi này thành chuỗi kia bằng các phép đột biến.

Grace đang phân tích hai chuỗi ADN \(a\) và \(b\), mỗi chuỗi có \(n\) phần tử được đánh chỉ số từ \(0\) đến \(n-1\). Nhiệm vụ của bạn là giúp Grace trả lời \(q\) câu hỏi có dạng: khoảng cách đột biến giữa chuỗi con \(a[x..y]\) và chuỗi con \(b[x..y]\) là bao nhiêu? Ở đây, chuỗi con \(s[x..y]\) của chuỗi ADN \(s\) là dãy các ký tự liên tiếp của \(s\) có chỉ số từ \(x\) đến \(y\), bao gồm cả hai đầu mút. Nói cách khác, \(s[x..y]\) là dãy \(s[x]s[x+1]\ldots s[y]\).

Chi tiết cài đặt

Bạn cần cài đặt các hàm sau:

void init(std::string a, std::string b);

• a, b: các xâu độ dài \(n\), biểu diễn hai chuỗi ADN cần phân tích.
• Hàm này được gọi đúng một lần, trước mọi lời gọi tới get_distance.

int get_distance(int x, int y);

• x, y: chỉ số bắt đầu và kết thúc của các chuỗi con cần phân tích.
• Hàm cần trả về khoảng cách đột biến giữa \(a[x..y]\) và \(b[x..y]\).
• Hàm này được gọi đúng \(q\) lần.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n q.
• Dòng \(2\): a.
• Dòng \(3\): b.
• Dòng \(4+i\) (\(0\le i\le q-1\)): x y cho lời gọi get_distance thứ \(i\).

Dữ liệu ra

Trình chấm mẫu in câu trả lời theo định dạng sau:

• Dòng \(1+i\) (\(0\le i\le q-1\)): giá trị trả về của lời gọi get_distance thứ \(i\).

Ràng buộc

• \(1\le n,q\le 100\,000\).
• \(0\le x\le y\le n-1\).
• Mỗi ký tự của \(a\) và \(b\) là một trong các ký tự A, T và C.

Phân nhóm

Ví dụ

6 3
ATACAT
ACTATA
1 3
4 5
3 5

2
1
-1

init("ATACAT", "ACTATA")

Nguồn

IOI 2021, Ngày 2 — Mutating DNA (dna).