Поскольку астронавты из миссии BubbleCup XI закончили свою миссию на Луне и являются большими поклонниками известного певца, они решили провести некоторое время перед возвращением на Землю, и, таким образом, создали так называемую игру «Moonwalk challenge».
Командам астронавтов выдаются карты кратеров на Луне и прямых двунаправленных путей от одних кратеров к другим, безопасные для «лунной походки». Каждый из этих прямых путей окрашен в один цвет, и есть единственный путь между каждым из двух кратеров. Цель игры заключается в том, чтобы найти два кратера, такие, что заданный массив цветов появляется чаще всего как непрерывный подотрезок на пути между этими двумя кратерами (пересекающиеся вхождения должны быть учтены как два различных).
Чтобы помочь любимой команде одержать победу, необходимо составить программу, которая по заданной карте отвечает на запросы следующего типа: для двух кратеров и массива цветов ответит, сколько раз заданный массив появляется как непрерывный подотрезок на пути от первого кратера ко второму.
Все цвета являются строчными буквами латинского алфавита.