Գտնել հաջորդ տողը
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n տողերից կազմված ցանկ, յուրաքանչյուր s տողի համար նույն ցանկից պետք է պարզի նրա հաջորդ տողը t (ներառյալ այն դեպքը, երբ t համընկնում է s-ի հետ)։
Հաջորդ տողը تعریفվում է որպես այն ամենափոքր տողը, որը համընկնում է s տողի սկզբին։Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 100 000), որը սահմանում է տողերի քանակը ցանկում։Հաջորդ
n տողերում պարունակվում են այդ տողերը։ Յուրաքանչյուր տող կազմված է լատինական փոքրատառերից։Երաշխավորվում է, որ մուտքում ընդհանուր գտնվող նիշերի քանակը չի գերազանցում -ը։
Ելք
Յուրաքանչյուր
s տողի համար պետք է տպել մեկ տող, որն իր մեջ պարունակում է հաջորդ տողը t։Examples
Մուտք | Ելք |
5
abaca
aba
abacaba
bacab
dabacaba | aba
aba
aba
bacab
dabacaba |
Բացատրություն
"abaca" տողի համար հաջորդ տողը "aba" է։
"aba" տողի դեպքում հաջորդ տողը հենց "aba"-ն է։
"abacaba" տողի պարագայում հաջորդ տողը "aba" է։
"abcab" տողի համար հաջորդ տողը "bacab" է։
"dabacaba" տողի դեպքում հաջորդ տողը "dabacaba"-ն է։
Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB