Ամենաերկար ընդհանուր վերջավորության հարցումներ

(Rap battle)

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n տարբեր բառերից կազմված ցուցակ և q հարցվող բառերի ցանկ , պետք է գտնի այն բառը ցուցակից a, որը լեքսիկոգրաֆիական կարգով ամենափոքրն է, տարբերվում է w-ից և ունի w-ի հետ ամենաերկար ընդհանուր վերջավորությունը:

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը (2 ≤ n ≤ 25 000), որը ներկայացնում է ցուցակում եղած բառերի քանակը:

Հաջորդ n տողերում տրված են այդ բառերը: Բոլոր բառերը բաղկացած են դիտարկվող լեզվի փոքրատառատառ լատինատառ символներից, և ամեն բառի երկարությունը չի գերազանցում 30 նիշը:

Հաջորդ տողում տրված է q ամբողջ թիվը (1 ≤ q ≤ 25000), որը ներկայացնում է հարցվող բառերի քանակը:

Հաջորդ q տողերում տրվում են հարցվող բառերը:

Յուրաքանչյուր բառ բաղկացած է փոքրատառ լատինատառ символներից, և դրա երկարությունը չի գերազանցում 30 նիշը:

Ելք

Յուրաքանչյուր հարցվող բառի համար պետք է տպել մեկ տող, որտեղ ներկայացված կլինի ցուցակից այն լեքսիկոգրաֆիական կարգով ամենափոքր բառը, որը տարբերվում է հարցվող բառից և ունի նույն հարցվող բառի ամենաերկար ընդհանուր վերջավորությունը:

Օրինակներ