Генератор терминов

Формула имеет синтаксис, представленный на рисунке 1(a). Если формула соответствует определенному синтаксису, показанному на рисунке 1(b), мы говорим, что она находится в нормальной форме (NF).

Формула преобразуется в NF с использованием следующих правил переписывания, где F обозначает формулу, S — непустую последовательность формул, а s и s' — возможно, пустые последовательности формул. Применение правила переписывания q → r к формуле F означает замену части F, соответствующей шаблону q, на r, как показано на рисунке 2. Преобразование завершается, когда ни одно правило переписывания больше не может быть применено. Преобразование завершится для любой формулы, и результат будет уникальным, независимо от того, какие правила применяются к каким частям формулы и в каком порядке.

1. (+F) → F

2. (*F) → F

3. (+s(+S)s') → (+sSs')

4. (*s(*S)s') → (*sSs')

5. (*s(+FS)s') → (+(*sFs')(*s(+S)s'))

Пусть NF(F) будет нормальной формой формулы F. Задача заключается в том, чтобы написать генератор термов, который для данной формулы F и числа k выводит следующие k термов из NF(F) в порядке их появления в NF(F). Если термы заканчиваются, генератор продолжает с первого терма NF(F). Например, для F=(+(*(+(*ab)(+a))b)), NF(F)=(+(*abb)(*ab)), как показано на рисунке 2. Генерация первого терма из NF(F) дает (*abb). Генерация еще двух термов приводит к (*ab), (*abb). Обратите внимание, что если NF(F) содержит одинаковые термы, как в последнем примере в образце ввода/вывода, эти термы считаются различными.

Входные данные

Напишите генератор термов, который считывает наборы данных из стандартного ввода. Набор данных состоит из: F k_1 ... k_N 0, где n > 0, F — формула, а k_1 ... k_N — длинные целые числа, отличные от 0.

Каждый напечатанный терм начинается с новой строки, и между символами терма нет пробелов. Сгенерированные термы не выводятся, если k_i < 0. Пробелы могут свободно использоваться во вводе. Каждая формула F во вводе имеет не более 150 символов, и каждый терм NF(F) имеет не более 80 символов, не считая пробелов. Входные данные заканчиваются концом файла и корректны.

Выходные данные

Для каждого k_i, i = 1, n, программа генерирует следующие |k_i| термов из NF(F) и, если k_i > 0, выводит эти термы на стандартный вывод.