Sroriken Member

問題文

処理研には $N$ 人の部員が所属しており、$M$ 個の研究会があります。
また、部員には $1,2,3, \dots, N$ と番号が付いており、研究会には $1,2,3, \dots, M$ と番号が付いています。

現時点での、各部員と各研究会への所属の対応を表す表が、複数行からなる文字列 $S$ で与えられ、$i$ 行目の文字列の $j$ 番目の文字 を $S_{i,j}$ とします。
$S_{i,j}$ が 1 のとき、部員 $i$ は 研究会 $j$ に所属していることを、 $S_{i,j}$ が 0 のとき、部員 $i$ は 研究会 $j$ に所属していないことを表しています。

クエリが $Q$ 個与えられるので、順番に処理してください。 クエリは以下の $8$ 種類のいずれかです。

• 1 p : 部員 $p$ が所属している研究会の数を出力する。
• 2 c : 研究会 $c$ に所属している部員の数を出力する。
• 3 p c : 部員 $p$ が新たに研究会 $c$ に入会する。
• 4 p c : 部員 $p$ が研究会 $c$ から脱会する。
• 5 p q : 部員 $p$ 、部員 $q$ の双方が所属している研究会の数を出力する。
• 6 p q : 部員 $p$ 、部員 $q$ の少なくとも片方が所属している研究会の数を出力する。
• 7 p q : 部員 $p$ 、部員 $q$ の片方のみが所属している研究会の数を出力する。
• 8 p q : 部員 $p$ が所属していて、部員 $q$ が所属していない研究会の数を出力する。

制約

• $2 \leq N \leq 100$
• $1 \leq M \leq 60$
• $1 \leq Q \leq 100$
• $S_{i,j} \, (1 \leq i \leq N, 1\leq j \leq M)$ は 1 , 0 のいずれかである。
• $1 \leq p,q \leq N$
• $p \neq q$
• $1 \leq c \leq M$
• $3$ 番目の形式のクエリ 3 p c が与えられるとき、そのクエリを処理する前の時点で、部員 $p$ は 研究会 $c$ に所属していないことが保証される。
• $4$ 番目の形式のクエリ 4 p c が与えられるとき、そのクエリを処理する前の時点で、部員 $p$ は 研究会 $c$ に所属していることが保証される。
• $N,M,Q,p,q,c$ は全て整数

入力

N M
S_{1, 1}S_{1, 2}...S_{1, M}
S_{2, 1}S_{2, 2}...S_{2, M}
.
.
.
S_{N, 1}S_{N, 2}...S_{N, M}
Q
query_1
query_2
.
.
.
query_Q

• $1$ 行目に、部員数 $N$ 、研究会の数 $M$ が空白区切りで与えられます。
• $2$ 行目から$1+N$ 行目まで、各部員と各研究会への所属の対応を表す表が文字列で与えられます。
• $2+N$ 行目に、与えられるクエリの数 $Q$ が与えられます。
• $3+N$ 行目以降に、順にクエリが与えれます。
• $query_i$ は $i$ 個目のクエリであり、以下のいずれかの形式で与えられます。

1 p

2 c

3 p c

4 p c

5 p q

5 p q

6 p q

7 p q

8 p q

出力

$1,2,5,6,7,8$ 番目の形式のクエリ ( 1 p , 2 c , 5 p q , 6 p q , 7 p q , 8 p q ) の個数を $q$ 個として、 $q$ 行で出力してください。$i \, (1 \leq i \leq q)$ 行目には $i$ 個目の $1,2,5,6,7,8$ 番目の形式のクエリに対する答えを出力してください。

入力例 1

5 3
000
111
101
010
001
8
1 1
2 2
3 1 2
4 2 3
5 1 2
6 3 4
7 5 1
8 2 3

出力例 1

0
2
1
3
2
1

• $query_1$ では、部員 $1$ が所属している研究会は $0$ 個なので、 $0$ を出力します。
• $query_2$ では、研究会 $2$ に所属している部員は、 {部員 $2$, 部員 $4$} の $2$ 人なので、 $2$ を出力します。
• $query_3$ では、部員 $1$ が新たに研究会 $2$ に入会します。
• $query_4$ では、部員 $2$ が研究会 $3$ から脱会します。
• $query_5$ では、部員 $1$ 、部員 $2$ の双方が所属している研究会は、 {研究会 $2$} の $1$ 個なので、 $1$ を出力します。
• $query_6$ では、部員 $3$ 、部員 $4$ の少なくとも片方が所属している研究会は、 {研究会 $1$, 研究会 $2$, 研究会 $3$} の $3$ 個なので、 $3$ を出力します。
• $query_7$ では、部員 $5$ 、部員 $1$ の片方のみが所属している研究会は、 {研究会 $2$, 研究会 $3$} の $2$ 個なので、 $2$ を出力します。
• $query_8$ では、部員 $2$ が所属していて、部員 $3$ が所属していない研究会は、 {研究会 $2$} の $1$ 個なので、 $1$ を出力します。

入力例 2

3 4
1000
1111
1011
10
6 1 2
3 1 2
4 2 2
7 1 3
8 3 2
1 2
8 1 2
6 1 3
1 3
2 3

出力例 2

4
3
0
3
1
4
3
2