J. AND Components
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an array $$$A_1, A_2, \ldots, A_N$$$ consisting of $$$N$$$ integers, and $$$2$$$ binary strings $$$L$$$, $$$R$$$. There will be $$$Q$$$ updates, where in each update, the value of some element is changed. Before any updates and after each update, print the answer to the following problem:

Let's create an unoriented graph $$$G$$$ consisting of $$$N$$$ vertices. For each $$$i$$$, we add up to two edges:

  • With the maximum $$$j$$$ such that $$$j \lt i$$$, $$$A_j \And A_i \gt 0$$$, and $$$L_i = 1$$$ holds. If no such $$$j$$$ exists or $$$L_i = 0$$$, then we do not add this edge.
  • With the minimum $$$j$$$ such that $$$j \gt i$$$, $$$A_j \And A_i \gt 0$$$, and $$$R_i = 1$$$ holds. If no such $$$j$$$ exists or $$$R_i = 0$$$, then we do not add this edge.
Find the number of connected components in this graph.
Input
  • The first line contains one integer $$$T \ (1 \leq T \leq 10^4)$$$, the number of test cases.
  • Then, for each test case:
    • The first line contains two space-separated integers $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 10^5)$$$.
    • The second line contains $$$N$$$ space-separated integers $$$A_1, A_2, \ldots, A_N$$$ $$$(0 \leq A_i \leq 10^6)$$$.
    • The third line contains a string consisting of $$$N$$$ characters $$$L_1L_2\ldots L_N$$$ $$$(L_i \in \{0, 1\})$$$.
    • The fourth line contains a string consisting of $$$N$$$ characters $$$R_1R_2\ldots R_N$$$ $$$(R_i \in \{0, 1\})$$$.
    • Then, $$$Q$$$ lines follow, each in one of the following formats:
      • A $$$i$$$ $$$x$$$ $$$(1 \leq i \leq N, 0 \leq x \leq 10^6)$$$: Update the value of $$$A_i$$$ to $$$x$$$, i.e., $$$A_i := x$$$.
      • L $$$i$$$ $$$x$$$ $$$(1 \leq i \leq N, x \in \{0, 1\})$$$: Update the value of $$$L_i$$$ to $$$x$$$, i.e., $$$L_i := x$$$.
      • R $$$i$$$ $$$x$$$ $$$(1 \leq i \leq N, x \in \{0, 1\})$$$: Update the value of $$$R_i$$$ to $$$x$$$, i.e., $$$R_i := x$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

It is guaranteed that the sum of $$$Q$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test, print $$$Q + 1$$$ lines, each consisting of one integer, the number of connected components. Note that the first line is the answer before any updates take place!

Example
Input
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
Output
3
3
3
3
2
2
3
3
3
2