題目描述

 

格蕾絲是一個在新加坡一家生物信息學公司工作的生物學家。作為她工作的一部分，她分析各種生物的DNA 序列。DNA 序列被定義為由字符“A”、“T”和“C”組成的字符串。請注意，在此任務中，DNA 序列不包含字符"G"。

我們將突變定義為對 DNA 序列中的兩個元素進行的操作，其中交換了序列的兩個元素。例如，通過交換下列序列中粗體的字符"A"和"C"，這樣一次突變可以將 "ACTA" 轉換為 "AATC"。

兩個序列之間的突變距離就是將一個序列轉換為另一個序列所需的最小突變次數，如果無法通過使用突變將一個序列轉換為另一個序列，突變距離為 −1。

格蕾絲正在分析兩個 DNA 序列 a 和 b，兩者都由 n 元素組成，標示為 0 到 n − 1。

你的任務是幫助 Grace 回答 q 個問題：子串 a[x..y] 和子串 b[x..y] 之間的變異距離是多少？

這裡，DNA序列 s的子串 s[x..y]被定義為 s的連續字符序列，其索引值為 x到 y。換句話說， s[x..y]是序列 s[x]s[x + 1] ... s[y]。

 

a, b: 長度為 n的字符串, 表示要進行分析的兩個 DNA 序列。

x, y：要分析的子串的起始和結束索引值。

應該返回子串 a[x..y] 和 b[x..y] 之間的變異距離。

會重複輸入 x, y 查詢 q 次。

 

假設 a = "ATACAT", b = "ACTATA"。

x = 1, y = 3 時這個應該返回 a[1..3] 和 b[1..3] 之間的變異距離，即序列“TAC”和“CTA”。“TAC”可以通過 2 次突變轉換為“CTA”：TAC → CAT，然後是 CAT→ CTA，如果變異次數少於 2，則轉換是不可能的。因此，此調用應返回 2。

x = 4, y = 5 時應返回序列“AT”和“TA”之間的突變距離。“AT”可以通過一次突變轉化為“TA”，顯然至少需要一次突變。因此，此調用應返回 1。

最後，x = 3, y = 5 時由於無法通過任何突變序列將序列“CAT”轉換為“ATA”，因此該調用應返回 −1。

輸入格式

樣例評分程式按以下格式讀取輸入：

第 1 行: n q

第 2 行: a

第 3 行: b

第 4 + i ( 0 ≤ i ≤ q − 1) 行:  x y 值。

輸出格式

第 1 + i ( 0 ≤ i ≤ q − 1) 行: 第 i次查詢的變異距離。

Samples

6 3
ATACAT
ACTATA
1 3
4 5
3 5

2
1
-1

提示

限制

1 ≤ n, q ≤ 100 000

0 ≤ x ≤ y ≤ n − 1

Each character of a and b is one of "A", "T", and "C".

子任務

1. (21 分) y − x ≤ 2
2. (22 分) q ≤ 500, y − x ≤ 1000, a 和 b 中每個字母只會是 "A" 或 "T".
3. (13 分) a 和 b 中只包含字母 "A" 和 "T".
4. (28 分) q ≤ 500, y − x ≤ 1000
5. (16 分) 沒有其他附加限制。

原始資料

• Zero1 題號：a625
• Hydro 題號：Z0625
• Locale：zh_TW
• Display：open