给定一个由 $N$ 个整数组成的数组 $A_1, A_2, \dots, A_N$，以及两个二进制字符串 $L$ 和 $R$。接下来会有 $Q$ 次修改，每次修改会改变某个元素的值。在进行任何修改之前以及每次修改之后，请输出以下问题的答案：

我们构建一个包含 $N$ 个顶点的无向图 $G$。对于每个 $i$，我们最多添加两条边：

• 连接顶点 $i$ 与满足 $j < i$、$A_j \ \& \ A_i > 0$ 且 $L_i = 1$ 的最大 $j$。如果不存在这样的 $j$ 或者 $L_i = 0$，则不添加这条边。
• 连接顶点 $i$ 与满足 $j > i$、$A_j \ \& \ A_i > 0$ 且 $R_i = 1$ 的最小 $j$。如果不存在这样的 $j$ 或者 $R_i = 0$，则不添加这条边。

求该图中的连通分量个数。

输入格式

• 第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。
• 对于每个测试用例：
  • 第一行包含两个空格分隔的整数 $N$ 和 $Q$ ($1 \le N, Q \le 10^5$)。
  • 第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 10^6$)。
  • 第三行包含一个由 $N$ 个字符组成的字符串 $L_1 L_2 \dots L_N$ ($L_i \in \{0, 1\}$)。
  • 第四行包含一个由 $N$ 个字符组成的字符串 $R_1 R_2 \dots R_N$ ($R_i \in \{0, 1\}$)。
  • 接下来 $Q$ 行，每行采用以下格式之一：
    • A i x ($1 \le i \le N, 0 \le x \le 10^6$)：将 $A_i$ 的值修改为 $x$，即 $A_i := x$。
    • L i x ($1 \le i \le N, x \in \{0, 1\}$)：将 $L_i$ 的值修改为 $x$，即 $L_i := x$。
    • R i x ($1 \le i \le N, x \in \{0, 1\}$)：将 $R_i$ 的值修改为 $x$，即 $R_i := x$。

保证所有测试用例中 $N$ 的总和不超过 $10^5$。

保证所有测试用例中 $Q$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出 $Q+1$ 行，每行包含一个整数，表示连通分量的数量。请注意，第一行是在进行任何修改之前的答案！

样例

输入样例 1

2
5 4
1 2 4 1 1
10101
11011
A 1 4
A 1 1
L 2 0
A 5 3
4 4
1 1 1 0
1111
1111
A 2 2
R 1 0
L 4 0
A 4 1

输出样例 1

3
3
3
3
2
2
3
3
3
2