Генератор імен#11539

Генератор імен

3 секунди

256 мегабайтів

Середня

Придумати назву для задачі у Polygon (система для підготовки задач) досить складно. Тому виникла потреба автоматизувати цей процес, створивши генератор імен.

Назва кожної задачі повинна складатися з трьох частин (у такому порядку): префікса, розділювача (символа "_" — підкреслення) та суфікса. Наприклад: "amazing_pascal", "clever_einstein", "magical_tesla". Префікс і суфікс — це слова, що складаються лише з маленьких латинських літер. Префікс обирається зі словника префіксів, а суфікс — зі словника суфіксів.

Вам надано $n$ слів із словника префіксів та $m$ слів із словника суфіксів. Також дано $k$ цілих чисел $q_{i}$ q_i — номери назв, які потрібно згенерувати. Щоб отримати назву з номером $q_{i}$ q_i, знайдіть $q_{i}$ q_i-у назву (нумерація починається з $1$ ) серед усіх можливих $n \times m$ n \times m назв (кожна має вигляд "префікс_суфікс"), відсортованих у лексикографічному порядку.

Вхідні дані

У першому рядку задано три цілих числа: $n$ , $m$ і $k$ ( $1 \leq n, m, k \leq 1 0^{5}$ 1 \le n, m, k \le 10^5) — відповідно розміри словника префіксів, словника суфіксів і кількість назв, які потрібно згенерувати.

У кожному з наступних $n$ рядків міститься рядок $a_{i}$ a_i ( $1 \leq ∣ a_{i} ∣ \leq 16$ 1 \le |a_i| \le 16) — слово зі словника префіксів, яке складається лише з маленьких латинських літер. Гарантується, що всі слова у словнику префіксів різні.

У кожному з наступних $m$ рядків міститься рядок $b_{i}$ b_i ( $1 \leq ∣ b_{i} ∣ \leq 16$ 1 \le |b_i| \le 16) — слово зі словника суфіксів, яке складається лише з маленьких латинських літер. Гарантується, що всі слова у словнику суфіксів різні.

У наступному рядку містяться $k$ цілих чисел $q_{i}$ q_i ( $1 \leq q_{i} \leq n \cdot m$ 1 \le q_i \le n \cdot m) — потрібні номери назв для генерації.

Позначення $∣ x ∣$ тут означає довжину рядка $x$ .

Вихідні дані

Виведіть $k$ рядків. У $i$ -му рядку виведіть назву задачі з номером $q_{i}$ q_i.

Приклади

Рядок $s$ лексикографічно менший за рядок $t$ тоді і лише тоді, коли існує таке $p$ , що $s_{i} = t_{i}$ s_i = t_i для всіх $i < p$ i < p і $s_{p} < t_{p}$ s_p < t_p (або $p > ∣ s ∣$ p > |s|, $p \leq ∣ t ∣$ p \le |t|).

Зверніть увагу: символ "_" лексикографічно менший за будь-яку маленьку латинську літеру.

Приклад 1