{"raw_statement":[{"iden":"statement","content":"There are _n_ phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct.\n\nThere is the latest version of Berdroid OS installed on Polycarp's phone. If some number is entered, is shows up all the numbers in the contacts for which there is a substring equal to the entered sequence of digits. For example, is there are three phone numbers in Polycarp's contacts: 123456789, 100000000 and 100123456, then:\n\n*   if he enters 00 two numbers will show up: 100000000 and 100123456,\n*   if he enters 123 two numbers will show up 123456789 and 100123456,\n*   if he enters 01 there will be only one number 100123456.\n\nFor each of the phone numbers in Polycarp's contacts, find the minimum in length sequence of digits such that if Polycarp enters this sequence, Berdroid shows this only phone number."},{"iden":"input","content":"The first line contains single integer _n_ (1 ≤ _n_ ≤ 70000) — the total number of phone contacts in Polycarp's contacts.\n\nThe phone numbers follow, one in each line. Each number is a positive 9-digit integer starting with a digit from 1 to 9. All the numbers are distinct."},{"iden":"output","content":"Print exactly _n_ lines: the _i_\\-th of them should contain the shortest non-empty sequence of digits, such that if Polycarp enters it, the Berdroid OS shows up only the _i_\\-th number from the contacts. If there are several such sequences, print any of them."},{"iden":"examples","content":"Input\n\n3\n123456789\n100000000\n100123456\n\nOutput\n\n9\n000\n01\n\nInput\n\n4\n123456789\n193456789\n134567819\n934567891\n\nOutput\n\n2\n193\n81\n91"}],"translated_statement":[{"iden":"statement","content":"Polycarp 的手机通讯录中有 #cf_span[n] 个电话号码。每个号码是一个 9 位整数，且首位数字不为 #cf_span[0]。所有号码互不相同。\n\nPolycarp 的手机安装了最新版本的 Berdroid 操作系统。当输入某个数字序列时，系统会显示通讯录中所有包含该序列作为子串的电话号码。例如，若 Polycarp 的通讯录中有三个号码：#cf_span[123456789]、#cf_span[100000000] 和 #cf_span[100123456]，则：\n\n对于 Polycarp 通讯录中的每个电话号码，找出最短的数字序列，使得当 Polycarp 输入该序列时，Berdroid 系统仅显示该号码。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 70000]）——Polycarp 通讯录中电话号码的总数。\n\n接下来每行一个电话号码，每个号码均为从 #cf_span[1] 到 #cf_span[9] 开头的正 9 位整数，所有号码互不相同。\n\n请输出恰好 #cf_span[n] 行：第 #cf_span[i] 行应包含一个最短的非空数字序列，使得当 Polycarp 输入该序列时，Berdroid 系统仅显示通讯录中的第 #cf_span[i] 个号码。若存在多个这样的序列，输出任意一个即可。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 70000]）——Polycarp 通讯录中电话号码的总数。接下来每行一个电话号码，每个号码均为从 #cf_span[1] 到 #cf_span[9] 开头的正 9 位整数，所有号码互不相同。"},{"iden":"output","content":"请输出恰好 #cf_span[n] 行：第 #cf_span[i] 行应包含一个最短的非空数字序列，使得当 Polycarp 输入该序列时，Berdroid 系统仅显示通讯录中的第 #cf_span[i] 个号码。若存在多个这样的序列，输出任意一个即可。"},{"iden":"examples","content":"输入\n3\n123456789\n100000000\n100123456\n输出\n9\n0000\n1\n\n输入\n4\n123456789\n193456789\n134567819\n934567891\n输出\n2\n193\n8\n191"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 70000 $, be the number of phone contacts.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ be a set of distinct 9-digit strings, where each $ p_i \\in \\{1,2,\\dots,9\\} \\times \\{0,1,\\dots,9\\}^8 $.\n\nFor any string $ s \\in \\{0,1,\\dots,9\\}^* $, define the query function:  \n$$ Q(s) = \\{ p \\in P \\mid s \\text{ is a contiguous substring of } p \\} $$\n\n**Constraints**  \nFor all $ i \\neq j $, $ p_i \\neq p_j $.\n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $, find a string $ s_i \\in \\{0,1,\\dots,9\\}^+ $ of minimal length such that:  \n$$ Q(s_i) = \\{p_i\\} $$  \nOutput any such $ s_i $ if multiple exist.","simple_statement":null,"has_page_source":false}