Trong một nhà máy dị hình có một công cụ gọi là bộ xoay. Mỗi lần sử dụng, bộ xoay có thể dịch vòng một xâu con nhị phân có độ dài đúng bằng \(3\): thay xyz bằng yzx hoặc zxy.

Cho hai xâu nhị phân \(s,t\) cùng độ dài \(n\). Có \(q\) truy vấn; mỗi truy vấn cho hai chỉ số \(l,r\). Hãy tìm số lần sử dụng bộ xoay ít nhất để biến \(s[l..r]\) thành \(t[l..r]\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(n,q\), lần lượt là độ dài của \(s,t\) và số truy vấn.
• Dòng thứ hai chứa xâu nhị phân \(s\) có độ dài \(n\).
• Dòng thứ ba chứa xâu nhị phân \(t\) có độ dài \(n\).
• Mỗi dòng trong \(q\) dòng tiếp theo chứa hai số nguyên dương \(l,r\) mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in một số nguyên trên một dòng: số lần sử dụng bộ xoay ít nhất. Nếu không thể biến đổi được, in -1.

Ràng buộc

Chấm điểm

Tính chất A: với mọi \(1\le i\le \left\lfloor\frac{n+1}{2}\right\rfloor\), ta có \(s_{2i-1}=t_{2i-1}=0\).

Ví dụ

10 5
1010111000
1111000001
1 6
3 5
4 5
1 10
8 9

3
1
-1
5
0

Đối với truy vấn đầu tiên, có thể thực hiện ba thao tác sau:

1. Chọn đoạn \([4,6]\), thay 011 bằng 110, thu được 101110.
2. Chọn đoạn \([2,4]\), thay 011 bằng 110, thu được 111010.
3. Chọn đoạn \([4,6]\), thay 010 bằng 100, thu được 111100.

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.