Double Strings

2000ms

262144K

Description:

You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$ of length at most $$$\mathbf{8}$$$.

For each string $$$s_i$$$, determine if there exist two strings $$$s_j$$$ and $$$s_k$$$ such that $$$s_i = s_j + s_k$$$. That is, $$$s_i$$$ is the concatenation of $$$s_j$$$ and $$$s_k$$$. Note that $$$j$$$ can be equal to $$$k$$$.

Recall that the concatenation of strings $$$s$$$ and $$$t$$$ is $$$s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$$$, where $$$p$$$ and $$$q$$$ are the lengths of strings $$$s$$$ and $$$t$$$ respectively. For example, concatenation of "code" and "forces" is "codeforces".

Input:

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of strings.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains non-empty string $$$s_i$$$ of length at most $$$\mathbf{8}$$$, consisting of lowercase English letters. Among the given $$$n$$$ strings, there may be equal (duplicates).

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output:

For each test case, output a binary string of length $$$n$$$. The $$$i$$$-th bit should be $$$\texttt{1}$$$ if there exist two strings $$$s_j$$$ and $$$s_k$$$ where $$$s_i = s_j + s_k$$$, and $$$\texttt{0}$$$ otherwise. Note that $$$j$$$ can be equal to $$$k$$$.

Sample Input:

3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code

Sample Output:

10100
011
10100101

Note:

In the first test case, we have the following:

$$$s_1 = s_2 + s_2$$$, since $$$\texttt{abab} = \texttt{ab} + \texttt{ab}$$$. Remember that $$$j$$$ can be equal to $$$k$$$.
$$$s_2$$$ is not the concatenation of any two strings in the list.
$$$s_3 = s_2 + s_5$$$, since $$$\texttt{abc} = \texttt{ab} + \texttt{c}$$$.
$$$s_4$$$ is not the concatenation of any two strings in the list.
$$$s_5$$$ is not the concatenation of any two strings in the list.

Since only $$$s_1$$$ and $$$s_3$$$ satisfy the conditions, only the first and third bits in the answer should be $$$\texttt{1}$$$, so the answer is $$$\texttt{10100}$$$.

Informação

Provedor Codeforces

Código CF1703D