D. Двойные строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ строк $$$s_1, s_2, \dots, s_n$$$ длины не более $$$\mathbf{8}$$$.

Для каждой строки $$$s_i$$$, проверьте, существуют ли такие $$$s_j$$$ и $$$s_k$$$, что $$$s_i = s_j + s_k$$$. То есть определите, является ли $$$s_i$$$ конкатенацией $$$s_j$$$ и $$$s_k$$$. Обратите внимание, что $$$j$$$ может быть равным $$$k$$$.

Напомним, что конкатенацией строк $$$s$$$ и $$$t$$$ называется строка $$$s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$$$, где $$$p$$$ и $$$q$$$ длины строк $$$s$$$ и $$$t$$$ соответственно. Например, конкатенация строк «code» и «forces» равна «codeforces».

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

Первая строка содержит одно число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество строк.

Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит непустую строку $$$s_i$$$ длины не более $$$\mathbf{8}$$$, состоящую из строчных английских букв. Среди заданных $$$n$$$ строк могут быть одинаковые.

Сумма $$$n$$$ по всем наборам не превосходит $$$10^5$$$.

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

Для каждого набора выведите бинарную строку длины $$$n$$$. $$$i$$$-й бит строки должен равняться $$$\texttt{1}$$$ если существуют две строки $$$s_j$$$ и $$$s_k$$$ таких, чтобы $$$s_i = s_j + s_k$$$, или же $$$\texttt{0}$$$ в противном случае. Обратите внимание, что $$$j$$$ может совпадать с $$$k$$$.

Пример
Входные данные
3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code
Выходные данные
10100
011
10100101
Примечание

В первом наборе мы имеем следующее:

  • $$$s_1 = s_2 + s_2$$$, так как $$$\texttt{abab} = \texttt{ab} + \texttt{ab}$$$. Помните, что $$$j$$$ может совпадать с $$$k$$$.
  • $$$s_2$$$ не может быть представлена как конкатенация никаких двух строк.
  • $$$s_3 = s_2 + s_5$$$, так как $$$\texttt{abc} = \texttt{ab} + \texttt{c}$$$.
  • $$$s_4$$$ не может быть представлена как конкатенация никаких двух строк.
  • $$$s_5$$$ не может быть представлена как конкатенация никаких двух строк.
Так как только $$$s_1$$$ и $$$s_3$$$ удовлетворяют условиям, то только первый и третий биты в ответе будут равняться $$$\texttt{1}$$$, поэтому ответ — $$$\texttt{10100}$$$.