С новым годом! 2020 год также известен как год Gyeongja (경자년, gyeongja-nyeon) в Корее. Откуда это имя? Кратко рассмотрим систему Gapja, которая традиционно используется в Корее для обозначения лет.

Существует две последовательности строк, $$$n$$$ строк $$$s_1, s_2, s_3, \ldots, s_{n}$$$ и $$$m$$$ строк $$$t_1, t_2, t_3, \ldots, t_{m}$$$. Эти строки состоят только из строчных букв алфавита. Среди этих строк могут быть одинаковые.

Назовем конкатенацией двух строк $$$x$$$ и $$$y$$$ такую строку, которая получится при последовательной записи сначала $$$x$$$, затем $$$y$$$ друг за другом, не меняя порядок символов в них. Например, конкатенация строк «code» и «forces» равна строке «codeforces».

Год 1 начинается с конкатенации двух строк $$$s_1$$$ и $$$t_1$$$. Если год увеличивается на один, то мы берем следующую строку по порядку для каждой соответствующей последовательности. Если используемая в данный момент строка находится в конце массива, то переходим к первой строке.

Например, если $$$n = 3, m = 4, s = $$${«a», «b», «c»}, $$$t =$$$ {«d», «e», «f», «g»}, то строки для лет с 1 по 14 - {«ad», «be», «cf», «ag», «bd», «ce», «af», «bg», «cd», «ae», «bf», «cg», «ad», «be»}. Обратите внимание, что название года может повторяться.

Вам даются две последовательности строк размером $$$n$$$ и $$$m$$$, а также $$$q$$$ запросов. Для каждого запроса вам будет указан год. Можете ли вы найти имена, соответствующие данным годам, согласно системе Gapja?