Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×
E. Перехват ячейки памяти
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть два потока, $$$\texttt{A}$$$ и $$$\texttt{B}$$$, и одна общая ячейка памяти. Изначально ячейка памяти содержит $$$0$$$.

У потока $$$\texttt{A}$$$ есть фиксированная последовательность команд $$$s$$$ длины $$$n$$$, а у потока $$$\texttt{B}$$$ — фиксированная последовательность команд $$$t$$$ длины $$$m$$$. Каждая команда является либо командой $$$\texttt{READ}$$$, обозначаемой $$$\texttt{R}$$$, либо командой $$$\texttt{WRITE}$$$, обозначаемой $$$\texttt{W}$$$.

Команды каждого потока должны выполняться в исходном порядке. Однако команды двух потоков можно произвольным образом чередовать. Иными словами, фактическое выполнение представляет собой общую последовательность из $$$n+m$$$ команд, полученную слиянием $$$s$$$ и $$$t$$$ с сохранением порядка команд внутри каждой строки.

Например, пусть $$$s=$$$ $$$\texttt{RWW}$$$, а $$$t=$$$ $$$\texttt{WR}$$$.

  • Последовательность $$$ s_1,t_1,s_2,t_2,s_3 $$$ является допустимым чередованием. Соответствующая общая последовательность команд имеет вид $$$\texttt{RWWRW}$$$.

  • Последовательность $$$ s_2,t_1,s_1,t_2,s_3 $$$ не является допустимым чередованием, поскольку команды $$$s$$$ выполняются не в исходном порядке.

  • Последовательность $$$ s_1,t_1,s_2,t_2 $$$ не является допустимым чередованием, поскольку в ней выполняются не все команды.

У общего выполнения есть временные метки. До выполнения какой-либо команды временная метка равна $$$0$$$. Команда, выполняемая на позиции $$$i$$$ в общей последовательности, имеет временную метку $$$i$$$.

  • Когда команда $$$\texttt{WRITE}$$$ выполняется с временной меткой $$$i$$$, она записывает значение $$$i$$$ в общую ячейку памяти.
  • Когда выполняется команда $$$\texttt{READ}$$$, она считывает текущее значение временной метки, хранящееся в общей ячейке памяти.

Для каждой команды $$$\texttt{READ}$$$, встречающейся в $$$s$$$ или $$$t$$$, определите, сколько различных значений она может считать по всем допустимым чередованиям двух последовательностей команд.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — длины последовательностей команд потоков $$$\texttt{A}$$$ и $$$\texttt{B}$$$ соответственно.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$ — последовательность команд потока $$$\texttt{A}$$$.

Третья строка содержит строку $$$t$$$ длины $$$m$$$ — последовательность команд потока $$$\texttt{B}$$$.

Каждый символ строк $$$s$$$ и $$$t$$$ является либо $$$\texttt{R}$$$, либо $$$\texttt{W}$$$. Каждая из строк $$$s$$$ и $$$t$$$ содержит хотя бы один символ $$$\texttt{R}$$$.

Гарантируется, что сумма всех $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, а сумма всех $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите две строки.

Первая строка содержит последовательность целых чисел, представляющих ответ для каждой команды $$$\texttt{READ}$$$, встречающейся в $$$s$$$, в порядке их появления. Длина последовательности должна быть равна количеству букв $$$\texttt{R}$$$ в $$$s$$$.

Вторая строка содержит последовательность целых чисел, представляющих ответ для каждой команды $$$\texttt{READ}$$$, встречающейся в $$$t$$$, в порядке их появления. Длина последовательности должна быть равна количеству букв $$$\texttt{R}$$$ в $$$t$$$.

Пример
Входные данные
3
1 1
R
R
1 2
R
WR
3 3
WRW
RWR
Выходные данные
1 
1 
2 
2 
4 
3 4
Примечание

В первом примере обе команды $$$\texttt{R}$$$ могут получить только изначально записанное в ячейке значение $$$0$$$, поэтому оба ответа равны $$$1$$$.

Во втором примере существует $$$3$$$ различных чередования (красной буквой $$$\texttt{R}$$$ обозначена команда из $$$s$$$):

  • $$$\mathtt{\color{red}{R}WR}$$$: первая команда $$$\texttt{R}$$$ считывает $$$0$$$, а вторая команда $$$\texttt{R}$$$ считывает $$$2$$$;
  • $$$\mathtt{W\color{red}{R}R}$$$: первая команда $$$\texttt{R}$$$ считывает $$$1$$$, а вторая команда $$$\texttt{R}$$$ считывает $$$1$$$;
  • $$$\mathtt{WR\color{red}{R}}$$$: первая команда $$$\texttt{R}$$$ считывает $$$1$$$, а вторая команда $$$\texttt{R}$$$ считывает $$$1$$$;

Таким образом, обе команды $$$\texttt{R}$$$ могут увидеть $$$2$$$ различных значения.