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

У вас есть бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$, и Айрис дал вам другую бинарную строку $$$r$$$ длины $$$n-1$$$.

Айрис собирается сыграть с вами в игру. В ходе игры вы выполните $$$n-1$$$ операций над $$$s$$$. В $$$i$$$-й операции ($$$1 \le i \le n-1$$$):

  1. Сначала вы выбираете индекс $$$k$$$ такой, что $$$1\le k\le |s| - 1$$$ и $$$s_{k} \neq s_{k+1}$$$. Если выбрать такой индекс невозможно, вы проигрываете;
  2. Затем вы заменяете $$$s_ks_{k+1}$$$ на $$$r_i$$$. Обратите внимание, что это уменьшает длину $$$s$$$ на $$$1$$$.

Если все $$$n-1$$$ операций выполнены успешно, вы выигрываете.

Определите, возможно ли вам выиграть в этой игре.

$$$^{\text{∗}}$$$Бинарная строка — это строка, в которой каждый символ равен либо $$$\mathtt{0}$$$, либо $$$\mathtt{1}$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 10^5$$$) — длину $$$s$$$.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$ ($$$s_i=\mathtt{0}$$$ или $$$\mathtt{1}$$$).

Третья строка каждого набора входных данных содержит бинарную строку $$$r$$$ длины $$$n-1$$$ ($$$r_i=\mathtt{0}$$$ или $$$\mathtt{1}$$$).

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

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

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

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

Пример
Входные данные
6
2
11
0
2
01
1
4
1101
001
6
111110
10000
6
010010
11010
8
10010010
0010010
Выходные данные
NO
YES
YES
NO
YES
NO
Примечание

В первом наборе входных данных вы не можете выполнить первую операцию. Таким образом, вы проигрываете.

Во втором наборе входных данных вы можете выбрать $$$k=1$$$ в единственной операции, и после этого $$$s$$$ станет равным $$$\mathtt{1}$$$. Таким образом, вы выигрываете.

В третьем наборе входных данных вы можете выполнить следующие операции: $$$\mathtt{1}\underline{\mathtt{10}}\mathtt{1}\xrightarrow{r_1=\mathtt{0}} \mathtt{1}\underline{\mathtt{01}} \xrightarrow{r_2=\mathtt{0}} \underline{\mathtt{10}} \xrightarrow{r_3=\mathtt{1}} \mathtt{1}$$$.