Вам даны \(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».
Выходные данные
Для каждого набора выведите бинарную строку длины \(n\). \(i\)-й бит строки должен равняться \(\texttt{1}\) если существуют две строки \(s_j\) и \(s_k\) таких, чтобы \(s_i = s_j + s_k\), или же \(\texttt{0}\) в противном случае. Обратите внимание, что \(j\) может совпадать с \(k\).
Примечание
В первом наборе мы имеем следующее:
- \(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}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code
|
10100
011
10100101
|