858D.md (1840B)
1 Source: https://codeforces.com/problemset/problem/858/D 2 3 D. Polycarp's phone book 4 5 time limit per test 6 7 4 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 There 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: 24 25 * if he enters 00 two numbers will show up: 100000000 and 100123456, 26 * if he enters 123 two numbers will show up 123456789 and 100123456, 27 * if he enters 01 there will be only one number 100123456. 28 29 For 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. 30 31 Input 32 33 The first line contains single integer *n* (1 ≤ *n* ≤ 70000) — the total number of phone contacts in Polycarp's contacts. 34 35 The 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. 36 37 Output 38 39 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. 40 41 Examples 42 43 Input 44 45 ``` 46 3 47 123456789 48 100000000 49 100123456 50 ``` 51 52 Output 53 54 ``` 55 9 56 000 57 01 58 ``` 59 60 Input 61 62 ``` 63 4 64 123456789 65 193456789 66 134567819 67 934567891 68 ``` 69 70 Output 71 72 ``` 73 2 74 193 75 81 76 91 77 ```