题目描述

有 $n$ 个长度相同的 01 序列，编号为 $1$ 到 $n$。

接下来有 $q$ 次询问，每次给出两个编号 $x,y$，请你求出第 $x$ 个序列和第 $y$ 个序列有多少个位置不同。

例如，10110 和 10001 有第 $3,4,5$ 三个位置不同，所以答案为 $3$。

本题适合练习 bitset 的异或运算。两个 01 序列不同的位置可以用 a[x] ^ a[y] 得到，再用 count() 统计 1 的个数。

输入格式

第一行三个整数 $n,m,q$，表示序列个数、每个序列的长度、询问次数。

接下来 $n$ 行，每行一个长度为 $m$ 的 01 字符串。

接下来 $q$ 行，每行两个整数 $x,y$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示两个序列不同的位置数量。

样例

3 5 3
10110
10001
11110
1 2
1 3
2 3

3
1
4

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le m \le 1000$，$1 \le q \le 100000$。

提示：可以用 bitset<1000> 存储每个 01 序列。