Cho hai mảng và gồm số.
Độ tương đồng giữa hai mảng được định nghĩa là số phép toán tối thiểu cần áp dụng để làm cho hai mảng bằng nhau. Nếu không thể làm cho chúng bằng nhau, độ tương đồng là .
Mỗi phép toán cho phép chọn một mảng con có độ dài cố định , và thay đổi mọi phần tử trong mảng con đó thành , với có thể chọn tùy ý. Ký hiệu là phép toán XOR bitwise.
Bạn cần tính toán độ tương đồng của hai mảng sau mỗi lần sửa đổi.
Dữ liệu:
Dòng đầu tiên chứa ba số , và (, ) — độ dài của các mảng, độ dài của các mảng con được áp dụng phép toán, và số lượng truy vấn.
Dòng thứ hai chứa số nguyên () — các phần tử của mảng .
Dòng thứ ba chứa số nguyên () — các phần tử của mảng .
Mỗi dòng trong số dòng tiếp theo mô tả một truy vấn và chứa một kí tự và hai số nguyên và (, ) — mảng mà truy vấn này thay đổi (a hoặc b), chỉ số của phần tử thay đổi và giá trị mới của nó.
Kết quả:
Trên dòng đầu tiên, in ra độ tương đồng ban đầu của các mảng và .
Trên dòng thứ trong dòng tiếp theo, in ra độ tương đồng của và sau khi áp dụng sửa đổi đầu tiên.
Ví du:
Dữ liệu:
3 3 1
0 4 2
1 2 3
b 2 5
Kết quả:
-1
1
Dữ liệu:
3 2 2
1 3 2
0 0 0
a 1 0
b 1 1
Kết quả:
2
-1
2
Giải thích:
Trong ví dụ đầu tiên, không thể làm cho mảng và bằng nhau với . Sau khi sửa đổi, có thể áp dụng phép toán với cho toàn bộ mảng thứ nhất (vì độ dài của nó bằng ), và nó sẽ bằng mảng thứ hai.
Trong ví dụ thứ hai, để làm cho các mảng bằng nhau trước khi thay đổi, có thể áp dụng phép toán với trên mảng con của và với trên mảng con của .
Sau tất cả các truy vấn, các mảng sẽ là và . Các phép toán tương tự làm cho chúng bằng nhau .
