B. Циншань любит строки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Циншань есть строка $$$s$$$, а у Даниэля — строка $$$t$$$. Обе строки содержат только символы $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

Строка $$$a$$$ длины $$$k$$$ является хорошей тогда и только тогда, когда

  • $$$a_i \ne a_{i+1}$$$ для всех $$$i=1,2,\ldots,k-1$$$.

Например, строки $$$\texttt{1}$$$, $$$\texttt{101}$$$, $$$\texttt{0101}$$$ — хорошие, а $$$\texttt{11}$$$, $$$\texttt{1001}$$$, $$$\texttt{001100}$$$ — плохие.

Циншань хочет сделать $$$s$$$ хорошей. Для этого она может выполнить следующую операцию любое количество раз (возможно, нулевое):

  • вставить $$$t$$$ в любую позицию $$$s$$$ (получив новую строку $$$s$$$).

Пожалуйста, скажите Циншань, можно ли сделать $$$s$$$ хорошей.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 50$$$) — длины строк $$$s$$$ и $$$t$$$ соответственно.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$.

Третья строка каждого набора входных данных содержит строку $$$t$$$ длины $$$m$$$.

Гарантируется, что $$$s$$$ и $$$t$$$ содержат только $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

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

Для каждого набора входных данных выведите «YES» (без кавычек), если можно сделать $$$s$$$ хорошей, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10
Выходные данные
Yes
Yes
No
No
No
Примечание

В первом наборе входных данных строка $$$s$$$ изначально хорошая, поэтому можно получить хорошую $$$s$$$, выполнив ноль операций.

Во втором наборе входных данных можно выполнить следующие две операции (вставленная строка $$$t$$$ подчеркнута):

  1. $$$\texttt{1}\underline{\texttt{010}}\texttt{11}$$$
  2. $$$\texttt{10101}\underline{\texttt{010}}\texttt{1}$$$

и получить $$$s = \texttt{101010101}$$$, что является хорошей строкой.

В третьем наборе входных данных нет способа сделать $$$s$$$ хорошей после любого количества операций.