Μετάλλαξη του DNA (dna)

Η Χαρά είναι βιολόγος και εργάζεται σε μια εταιρεία βιοπληροφορικής στη Σιγκαπούρη. Μέρος της δουλειάς της είναι η ανάλυση ακολουθιών DNA διαφόρων οργανισμών. Οι ακολουθίες DNA είναι συμβολοσειρές (string) αποτελούμενες από γράμματα "A", "T", και "C". Προσέξτε ότι σε αυτό το πρόβλημα οι ακολουθίες DNA δεν περιέχουν το γράμμα "G".

Ονομάζουμε μετάλλαξη την αντιμετάθεση δύο στοιχείων μίας ακολουθίας DNA. Για παράδειγμα μια απλή μετάλλαξη μπορεί να μετασχηματίσει την "ACTA" σε "AATC", αντιμεταθέτοντας τα έντονα σημειωμένα γράμματα "A" και "C".

Η απόσταση μετάλλαξης μεταξύ δυο ακολουθιών είναι το ελάχιστο πλήθος μεταλλάξεων που απαιτούνται για να μετασχηματισθεί μια ακολουθία σε μια άλλη, ή -~1~ αν δεν είναι δυνατόν να μετασχηματισθεί η μια ακολουθία στην άλλη χρησιμοποιώντας μεταλλάξεις.

Η Χαρά αναλύει δυο ακολουθίες DNA, την ~a~ και την ~b~, που αποτελούνται και οι δυο από n γράμματα αριθμημένα από ~0~ έως n -~1~. Το πρόβλημά σας είναι να τη βοηθήσετε να απάντήσει σε ~q~ ερωτήσεις της μορφής: ποιά είναι η απόσταση μετάλλαξης μεταξύ της υποακολουθίας ~a[x..y]~ και της υποακολουθίας ~b[x..y]~; Εδώ, ως υποακολουθία ~s[x..y]~ μιας ακολουθίας ~s~ ορίζεται μια ακολουθία διαδοχικών γραμμάτων της ~s~, με δείκτες από ~x~ έως ~y~ συμπεριλαμβανομένων. Δηλαδή, ~s[x..y]~ είναι η υπακολουθία ~s[x]s[x + 1] ... 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" με ~2~ μεταλλάξεις: TAC → CAT, ακολουθούμενη από την CAT → CTA, και ο μετασχηματισμός είναι αδύνατος με λιγότερες από ~2~ μεταλλάξεις.

Επομένως, αυτή η κλήση θα πρέπει να επιστρέψει 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 1\,000~, κάθε γράμμα των \(a και \)b~ είναι είτε "A" ή "T".
3. (~13~ βαθμοί) κάθε γράμμα των ~a~ και ~b~ είναι είτε "A" ή "T".
4. (~28~ βαθμοί) ~q \le 500, y - x \le 1\,000~
5. (~16~ βαθμοί) Χωρίς επιπλέον περιορισμούς.

Υποδειγματικός βαθμολογητής

Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής:

• γραμμή ~1~: ~n~ ~q~
• γραμμή ~2~: ~a~
• γραμμή ~3~: ~b~
• γραμμή ~4~ + ~i~ ( ~0 \le i \le q - 1~): ~x~ ~y~ για την ~i~-οστη κλήση της get_distance

Ο υποδειγματικός βαθμολογητής τυπώνει τις απαντήσεις σας με την ακόλουθη μορφή:

• γραμμή ~1~ + ~i~ ( ~0 \le i \le q - 1~) : η τιμή που επιστρέφεται από την ~i~-οστη κλήση της get_distance.