翻转（flip）

题目描述

苗苗在实验室中调试一排开关。开关的当前状态可以看作一个长度为 $n$ 的 01 字符串 $s$，目标状态为另一个长度为 $n$ 的 01 字符串 $t$。为了方便描述，字符串下标均从 $1$ 开始。

苗苗可以进行一种自动翻转操作：选择一个整数 $x$，满足 $1\le x\le n-k+1$，然后对所有 $x\le i\le x+k-1$ 执行

也就是说，苗苗每次可以翻转 $s$ 中一个长度恰好为 $k$ 的连续段。

在使用自动翻转操作之前，苗苗还可以手动改变若干个字符。一次手动改变可以选择一个位置 $i$，并执行

苗苗想知道：至少需要手动改变多少个字符，才能在此之后通过若干次自动翻转操作，使得 $s$ 变为 $t$。

实验过程中会发生 $q$ 次改变。第 $j$ 次改变给出一个区间 $[l_j,r_j]$，苗苗会先对当前的 $s$ 中所有 $l_j\le i\le r_j$ 的位置执行

这个改变是有后效性的，也就是说它会保留到之后的询问中。每次改变之后，你都需要回答上面的问题。

注意，询问中提到的“手动改变若干个字符”只用于计算这一次答案，不会真正修改之后的字符串 $s$。

形式化地，设当前字符串为 $s$。你需要求最小的整数 $c$，使得存在一个集合 $A\subseteq\{1,2,\dots,n\}$，满足 $|A|=c$，先对所有 $i\in A$ 翻转 $s_i$，再经过若干次长度为 $k$ 的连续段翻转后，可以使 $s=t$。

输入格式

从文件 flip.in 中读入数据。

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行三个整数 $n,k,q$。

第二行一个长度为 $n$ 的 01 字符串 $s$。

第三行一个长度为 $n$ 的 01 字符串 $t$。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次对当前字符串 $s$ 的区间翻转。

输出格式

输出到文件 flip.out 中。

对于每组测试数据，输出 $q$ 行，每行一个整数，表示对应改变之后的答案。

输入输出样例 #1

输入 #1

1
5 3 1
10001
11110
2 3

输出 #1

1

样例 #1 解释

样例中，第一次改变之后，当前字符串变为 11101。

若先把第 $3$ 个字符从 1 改成 0，字符串变为 11001，再翻转区间 $[3,5]$，即可得到目标字符串 11110。可以证明不手动改变字符无法做到，因此答案为 $1$。

输入输出样例 #2

输入 #2

1
4 1 3
0101
1010
1 4
2 2
3 4

输出 #2

0
0
0

样例 #2 解释

因为 $k=1$，每次自动翻转可以只改变一个字符，所以每次答案都是 $0$。

数据范围

对于所有数据，满足 $1\le T\le 5$，$1\le k\le n\le 2\times 10^5$，$1\le q\le 2\times 10^5$，$1\le l\le r\le n$。

本题共 $20$ 个测试点，每个测试点 $5$ 分。

样例文件