{"raw_statement":[{"iden":"statement","content":"You are given _n_ strings _s_1, _s_2, ..., _s__n_ consisting of characters 0 and 1. _m_ operations are performed, on each of them you concatenate two existing strings into a new one. On the _i_\\-th operation the concatenation _s__a__i__s__b__i_ is saved into a new string _s__n_ + _i_ (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer _k_ such that all possible strings consisting of 0 and 1 of length _k_ (there are 2_k_ such strings) are substrings of the new string. If there is no such _k_, print 0."},{"iden":"input","content":"The first line contains single integer _n_ (1 ≤ _n_ ≤ 100) — the number of strings. The next _n_ lines contain strings _s_1, _s_2, ..., _s__n_ (1 ≤ |_s__i_| ≤ 100), one per line. The total length of strings is not greater than 100.\n\nThe next line contains single integer _m_ (1 ≤ _m_ ≤ 100) — the number of operations. _m_ lines follow, each of them contains two integers _a__i_ abd _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_ + _i_ - 1) — the number of strings that are concatenated to form _s__n_ + _i_."},{"iden":"output","content":"Print _m_ lines, each should contain one integer — the answer to the question after the corresponding operation."},{"iden":"example","content":"Input\n\n5\n01\n10\n101\n11111\n0\n3\n1 2\n6 5\n4 4\n\nOutput\n\n1\n2\n0"},{"iden":"note","content":"On the first operation, a new string \"_0110_\" is created. For _k_ = 1 the two possible binary strings of length _k_ are \"_0_\" and \"_1_\", they are substrings of the new string. For _k_ = 2 and greater there exist strings of length _k_ that do not appear in this string (for _k_ = 2 such string is \"_00_\"). So the answer is 1.\n\nOn the second operation the string \"_01100_\" is created. Now all strings of length _k_ = 2 are present.\n\nOn the third operation the string \"_1111111111_\" is created. There is no zero, so the answer is 0."}],"translated_statement":[{"iden":"statement","content":"你被给定 #cf_span[n] 个由字符 #cf_span[0] 和 #cf_span[1] 组成的字符串 #cf_span[s1, s2, ..., sn]。执行 #cf_span[m] 次操作，每次操作将两个已有的字符串拼接成一个新的字符串。在第 #cf_span[i] 次操作中，拼接 #cf_span[saisbi] 得到的新字符串被保存为 #cf_span[sn + i]（操作编号从 #cf_span[1] 开始）。每次操作后，你需要找到最大的正整数 #cf_span[k]，使得所有长度为 #cf_span[k] 的由 #cf_span[0] 和 #cf_span[1] 组成的字符串（共有 #cf_span[2k] 个）都是新字符串的子串。如果不存在这样的 #cf_span[k]，则输出 #cf_span[0]。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 字符串的数量。接下来的 #cf_span[n] 行每行包含一个字符串 #cf_span[s1, s2, ..., sn] (#cf_span[1 ≤ |si| ≤ 100])。所有字符串的总长度不超过 #cf_span[100]。\n\n接下来一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 100]) —— 操作的数量。随后 #cf_span[m] 行，每行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n + i - 1]) —— 用于拼接形成 #cf_span[sn + i] 的两个字符串的编号。\n\n请输出 #cf_span[m] 行，每行一个整数 —— 对应每次操作后的答案。\n\n在第一次操作中，生成了新字符串 \"_0110_\"。对于 #cf_span[k = 1]，所有长度为 #cf_span[k] 的二进制字符串是 \"_0_\" 和 \"_1_\"，它们都是新字符串的子串。对于 #cf_span[k = 2] 及更大的值，存在长度为 #cf_span[k] 的字符串未出现在该字符串中（例如，当 #cf_span[k = 2] 时，字符串 \"_00_\" 就不存在）。因此答案是 #cf_span[1]。\n\n在第二次操作中，生成了字符串 \"_01100_\"。此时所有长度为 #cf_span[k = 2] 的字符串均已出现。\n\n在第三次操作中，生成了字符串 \"_1111111111_\"。该字符串中没有字符 '0'，因此答案是 #cf_span[0]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 字符串的数量。接下来的 #cf_span[n] 行每行包含一个字符串 #cf_span[s1, s2, ..., sn] (#cf_span[1 ≤ |si| ≤ 100])。所有字符串的总长度不超过 #cf_span[100]。接下来一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 100]) —— 操作的数量。随后 #cf_span[m] 行，每行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n + i - 1]) —— 用于拼接形成 #cf_span[sn + i] 的两个字符串的编号。"},{"iden":"output","content":"请输出 #cf_span[m] 行，每行一个整数 —— 对应每次操作后的答案。"},{"iden":"note","content":"在第一次操作中，生成了新字符串 \"_0110_\"。对于 #cf_span[k = 1]，所有长度为 #cf_span[k] 的二进制字符串是 \"_0_\" 和 \"_1_\"，它们都是新字符串的子串。对于 #cf_span[k = 2] 及更大的值，存在长度为 #cf_span[k] 的字符串未出现在该字符串中（例如，当 #cf_span[k = 2] 时，字符串 \"_00_\" 就不存在）。因此答案是 #cf_span[1]。在第二次操作中，生成了字符串 \"_01100_\"。此时所有长度为 #cf_span[k = 2] 的字符串均已出现。在第三次操作中，生成了字符串 \"_1111111111_\"。该字符串中没有字符 '0'，因此答案是 #cf_span[0]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the initial number of binary strings.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be the initial sequence of strings, where each $ s_i \\in \\{0,1\\}^* $.  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of operations.  \nFor $ i \\in \\{1, \\dots, m\\} $, operation $ i $ concatenates strings $ s_{a_i} $ and $ s_{b_i} $ to form $ s_{n+i} = s_{a_i} + s_{b_i} $.  \n\nLet $ \\mathcal{B}_k = \\{0,1\\}^k $ denote the set of all binary strings of length $ k $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100 $, $ 1 \\leq m \\leq 100 $  \n2. $ 1 \\leq |s_i| \\leq 100 $ for $ i \\in \\{1, \\dots, n\\} $, total initial length $ \\leq 100 $  \n3. For each operation $ i $: $ 1 \\leq a_i, b_i \\leq n + i - 1 $  \n\n**Objective**  \nAfter each operation $ i \\in \\{1, \\dots, m\\} $, compute the maximum integer $ k \\geq 0 $ such that $ \\mathcal{B}_k \\subseteq \\text{Substr}(s_{n+i}) $, where $ \\text{Substr}(s) $ is the set of all contiguous substrings of $ s $.  \nIf no such $ k > 0 $ exists, output $ 0 $.","simple_statement":null,"has_page_source":false}