Ամենաերկար ընդհանուր վերջավորության հարցումներ
(Rap battle)
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n տարբեր բառերից կազմված ցուցակ և q հարցվող բառերի ցանկ , պետք է գտնի այն բառը ցուցակից a, որը լեքսիկոգրաֆիական կարգով ամենափոքրն է, տարբերվում է w-ից և ունի w-ի հետ ամենաերկար ընդհանուր վերջավորությունը:Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (2 ≤ n ≤ 25 000), որը ներկայացնում է ցուցակում եղած բառերի քանակը:Հաջորդ
n տողերում տրված են այդ բառերը: Բոլոր բառերը բաղկացած են դիտարկվող լեզվի փոքրատառատառ լատինատառ символներից, և ամեն բառի երկարությունը չի գերազանցում 30 նիշը:Հաջորդ տողում տրված է
q ամբողջ թիվը (1 ≤ q ≤ 25000), որը ներկայացնում է հարցվող բառերի քանակը:Հաջորդ
q տողերում տրվում են հարցվող բառերը:Յուրաքանչյուր բառ բաղկացած է փոքրատառ լատինատառ символներից, և դրա երկարությունը չի գերազանցում 30 նիշը:
Ելք
Յուրաքանչյուր հարցվող բառի համար պետք է տպել մեկ տող, որտեղ ներկայացված կլինի ցուցակից այն լեքսիկոգրաֆիական կարգով ամենափոքր բառը, որը տարբերվում է հարցվող բառից և ունի նույն հարցվող բառի ամենաերկար ընդհանուր վերջավորությունը:
Օրինակներ
Input | Output |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB