Задача №113973. Словарь братьев по разуму
В фантастическом романе, который пишет Петя Торопыжкин, инопланетные существа используют алфавит, состоящий из двух символов
и 
Которые в рабочем варианте текста Петя представляет заглавными буквами
F
и
G
(для простоты). Петя даже составил словарь языка этих существ. Для быстроты поиска по словарю он выбрал целое число \(p\) и сопоставил каждому слову \(w=\alpha_0\alpha_1\ldots\alpha_k\) целое число \(h(w) = \sum_{i=0}^k a_i \cdot p^i\), где коэффициент \(a_i\) равен \(0\), если \(\alpha_i = F\), и \(1\), если \(\alpha_i = G\). Однако такое число может быть большим, поэтому Петя запоминает остаток от деления \(h(w)\) на некоторое другое целое число \(D\).
Такое число называется хешем слова \(w\), а правило вычисления хеша — хеш-функцией . Вычислив один раз хеши слов из словаря, дальше очень просто проверять их на несовпадение: если хеши двух слов различаются, то и сами слова совпадать не могут. А вот если хеши двух слов совпадают (такую ситуацию называют коллизией ), тогда для точной проверки эти слова надо сравнивать посимвольно.
Для быстрой работы со словарём надо написать программу, которая ищет в нём слова, чей хеш совпадает с заданным значением.
В первой строке через пробел заданы два целых числа \(p\) и \(D\), определяющие хеш-функцию (\(1 \leq p \leq 10^9\), \(1 \leq D \leq 2 \cdot 10^9\)). Во второй строке задано целое число \(H\) — требуемое значение хеша (\(0 \leq H < D\)). В третьей строке задано целое число \(n\) — количество слов в словаре (\(1 \leq n \leq 10^3\)). В следующих \(n\) строках заданы слова — непустые последовательности заглавных символов латиницы F и G длиной не более \(10^3\) символов.
Если слова с указанным хешем найдены, выведите в первой строке « FOUND », а затем найденные слова по одному в строке (в каком-либо порядке). Если таких слов не найдено, выведите в первой строке « NOT FOUND », а во второй через пробел наименьшее и наибольшее значения хешей слов словаря.
7 100 1 3 FFFFG FFG G
FOUND FFFFG G
7 100 10 3 FFFFG FFG G
NOT FOUND 1 49