С новым годом! 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?