Memory Cell Interception

There are two threads, A and B, and one shared memory cell. Initially, the memory cell contains 0.

Thread A has a fixed command sequence s of length n, and thread B has a fixed command sequence t of length m. Each command is either READ, denoted by R, or WRITE, denoted by 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= RWW and t= WR.

• The sequence s1,t1,s2,t2,s3 is a valid interleaving. The corresponding global command sequence is RWWRW.
• The sequence s2,t1,s1,t2,s3 is not a valid interleaving, because the commands of s are not executed in their original order.
• The sequence s1,t1,s2,t2 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 WRITE command is executed at timestamp i, it writes the value i into the shared memory cell.
• When a READ command is executed, it reads the current timestamp value stored in the shared memory cell.

For every 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≤t≤104). The description of the test cases follows.

The first line of each test case contains two integers n and m (1≤n,m≤2⋅105) — the lengths of the command sequences of threads A and B, respectively.

The second line contains a string s of length n — the command sequence of thread A.

The third line contains a string t of length m — the command sequence of thread B.

Each character of s and t is either R or W. Each of the strings s and t contains at least one character R.

It is guaranteed that the sum of all n over all test cases does not exceed 2⋅105, and the sum of all m over all test cases does not exceed 2⋅105.

Output

For each test case, print two lines.

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

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

Note

In the first example, both 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 R represents the one in s):

• RWR: the first R reads 0, the second R reads 2;
• WRR: the first R reads 1, the second R reads 1;
• WRR: the first R reads 1, the second R reads 1;

Above all, both R commands might see 2 distinct values.

3
1 1
R
R
1 2
R
WR
3 3
WRW
RWR

1 
1 
2 
2 
4 
3 4