E. Memory Cell Interception
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two threads, $$$\texttt{A}$$$ and $$$\texttt{B}$$$, and one shared memory cell. Initially, the memory cell contains $$$0$$$.

Thread $$$\texttt{A}$$$ has a fixed command sequence $$$s$$$ of length $$$n$$$, and thread $$$\texttt{B}$$$ has a fixed command sequence $$$t$$$ of length $$$m$$$. Each command is either $$$\texttt{READ}$$$, denoted by $$$\texttt{R}$$$, or $$$\texttt{WRITE}$$$, denoted by $$$\texttt{W}$$$.

The commands of each thread must be executed in their original order. However, commands from the two threads may be interleaved arbitrarily. In other words, the actual execution is a global sequence of $$$n+m$$$ commands obtained by merging $$$s$$$ and $$$t$$$ while preserving the order of commands inside each string.

For example, suppose $$$s=$$$ $$$\texttt{RWW}$$$ and $$$t=$$$ $$$\texttt{WR}$$$.

  • The sequence $$$ s_1,t_1,s_2,t_2,s_3 $$$ is a valid interleaving. The corresponding global command sequence is $$$\texttt{RWWRW}$$$.

  • The sequence $$$ s_2,t_1,s_1,t_2,s_3 $$$ is not a valid interleaving, because the commands of $$$s$$$ are not executed in their original order.

  • The sequence $$$ s_1,t_1,s_2,t_2 $$$ is not a valid interleaving, because it does not execute all commands.

The global execution has timestamps. Before any command is executed, the timestamp is $$$0$$$. The command executed at position $$$i$$$ in the global sequence has timestamp $$$i$$$.

  • When a $$$\texttt{WRITE}$$$ command is executed at timestamp $$$i$$$, it writes the value $$$i$$$ into the shared memory cell.
  • When a $$$\texttt{READ}$$$ command is executed, it reads the current timestamp value stored in the shared memory cell.

For every $$$\texttt{READ}$$$ command appearing in either $$$s$$$ or $$$t$$$, determine how many distinct values it can read over all valid interleavings of the two command sequences.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — the lengths of the command sequences of threads $$$\texttt{A}$$$ and $$$\texttt{B}$$$, respectively.

The second line contains a string $$$s$$$ of length $$$n$$$ — the command sequence of thread $$$\texttt{A}$$$.

The third line contains a string $$$t$$$ of length $$$m$$$ — the command sequence of thread $$$\texttt{B}$$$.

Each character of $$$s$$$ and $$$t$$$ is either $$$\texttt{R}$$$ or $$$\texttt{W}$$$. Each of the strings $$$s$$$ and $$$t$$$ contains at least one character $$$\texttt{R}$$$.

It is guaranteed that the sum of all $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of all $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print two lines.

The first line contains a sequence of integers, representing the answer for each $$$\texttt{READ}$$$ instruction appearing in $$$s$$$ in order. The length of the sequence must equal the number of letters $$$\texttt{R}$$$ in $$$s$$$.

The second line contains a sequence of integers, representing the answer for each $$$\texttt{READ}$$$ instruction appearing in $$$t$$$ in order. The length of the sequence must equal the number of letters $$$\texttt{R}$$$ in $$$t$$$.

Example
Input
3
1 1
R
R
1 2
R
WR
3 3
WRW
RWR
Output
1 
1 
2 
2 
4 
3 4
Note

In the first example, both $$$\texttt{R}$$$ commands can only get the value $$$0$$$ initially set in the cell, so the answers are both $$$1$$$.

In the second example, there are $$$3$$$ different interleavings (the red letter $$$\texttt{R}$$$ represents the one in $$$s$$$):

  • $$$\mathtt{\color{red}{R}WR}$$$: the first $$$\texttt{R}$$$ reads $$$0$$$, the second $$$\texttt{R}$$$ reads $$$2$$$;
  • $$$\mathtt{W\color{red}{R}R}$$$: the first $$$\texttt{R}$$$ reads $$$1$$$, the second $$$\texttt{R}$$$ reads $$$1$$$;
  • $$$\mathtt{WR\color{red}{R}}$$$: the first $$$\texttt{R}$$$ reads $$$1$$$, the second $$$\texttt{R}$$$ reads $$$1$$$;

Above all, both $$$\texttt{R}$$$ commands might see $$$2$$$ distinct values.