题目描述

给定一个 $n$ 行 $m$ 列的 01 矩阵。每一行都可以看成一个长度为 $m$ 的 01 序列。

接下来有 $q$ 次询问，每次给出一种运算和两行编号 $x,y$：

• AND x y：询问第 $x$ 行和第 $y$ 行按位与之后有多少个 1；
• OR x y：询问第 $x$ 行和第 $y$ 行按位或之后有多少个 1；
• XOR x y：询问第 $x$ 行和第 $y$ 行按位异或之后有多少个 1。

本题适合集中练习 bitset 的 &、|、^ 和 count()。

输入格式

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

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

接下来 $q$ 行，每行一个操作，格式为 AND x y、OR x y 或 XOR x y。

输出格式

对于每次询问，输出一行一个整数。

样例

3 5 4
10110
10001
11110
AND 1 2
OR 1 2
XOR 1 2
AND 1 3

1
4
3
3

数据范围与提示

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