Придумати назву завдання в полігоні (система для підготовки завдань) досить складно. Тому виникла необхідність автоматизувати цей процес, створивши генератор імен.
Назва будь-якої задачі має складатися з трьох частин (перерахованих за порядком): префікса, розділителя — символ «_
» (знак підкреслення) і суфікса. Приклади названих задач: «amazing_pascal
», «clever_einstein
», «magical_tesla
». Префікс і суфікс — слова, що складаються тільки зі маленьких літер латинського алфавіту, причому префікс вибирається тільки зі слів, що знаходяться в словнику префіксів, а суфікс — в словнику суфіксів.
Ви дали n слів, що знаходяться в словнику префіксів, і m слів, що знаходяться в словнику суфіксів. Вам також дано k цілих чисел qi — номерів назв, які потрібно згенерувати. Щоб згенерувати назву під номером qi, вам необхідно знайти назву qi (нумерація починається з 1), серед усіх можливих n×m назв, відсортованих у лексикографічному порядку.
У першому рядку задано три цілих числа n, m і k (1≤n,m,k≤105) — відповідно розмір префіксів словника, розмір суфіксів словника та кількість назв , яке потрібно згенерувати.
У кожному з наступних n рядків міститься рядок ai (1≤∣ai∣≤16) — слово з префіксів словника, що складається тільки зі маленької букви латинського алфавіту. Гарантується, що всі слова в словниках префіксів різні.
У кожному з наступних m рядків міститься рядок bi (1≤∣bi∣≤16) — слово зі словника суфіксів, що складається лише зі маленької букви латинського алфавіту. Гарантується, що всі слова в словнику суфіксів різні.
У наступному рядку завдання k цілого чисел qi (1≤qi≤n⋅m) — номери назв, які необхідно створити.
Запис ∣x∣ тут обозначає довжину рядка x.
Виведіть k рядок. У i-й рядку виведіть назву задачі під номером qi.
Рядок s лексикографічно менший рядка t тоді і тільки тоді, коли знайдеться таке p, що si=ti для i<p і sp<tp (або p>∣s∣, p≤∣t∣).
Зверніть увагу: символ «_
» лексикографічно менше будь-якої маленької латинської літери.