Решение задачи Новый год и названия с Codeforces

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

Существует две последовательности строк, n строк s1,s2,s3,…,sn и m строк t1,t2,t3,…,tm. Эти строки состоят только из строчных букв алфавита. Среди этих строк могут быть одинаковые.

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

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

Например, если 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?