Программа: модель исполнителя Редактор

Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор умеет выполнять две команды; в обеих командах v и w обозначают непустые цепочки цифр. заменить(v, w) — заменяет в строке первое слева вхождение цепочки v на цепочку w; нашлось(v) — проверяет, встречается ли цепочка v в строке Редактора (результат — «истина» или «ложь»). Дана программа для Редактора с n парами цепочек (v1, w1), …, (vn, wn):

ПОКА нашлось(v1) ИЛИ нашлось(v2) ИЛИ … ИЛИ нашлось(vn)
  ЕСЛИ нашлось(v1)
    ТО заменить(v1, w1)
    ИНАЧЕ ЕСЛИ нашлось(v2)
      ТО заменить(v2, w2)
      …
      ИНАЧЕ заменить(vn, wn)
КОНЕЦ ПОКА

Иначе говоря, на каждом шаге цикла выполняется ровно одна замена — для первой по порядку цепочки vi, которая есть в строке. Цикл заканчивается, когда ни одной из цепочек v1, …, vn в строке нет. Напишите программу, которая моделирует работу Редактора. Входные данные: в первой строке — исходная строка из цифр (длина от 1 до 300); во второй — число n (1 ≤ n ≤ 5); далее n строк, в i-й из них через пробел записаны цепочки vi и wi (непустые, из цифр, длиной не более 10). Гарантируется, что программа завершается не более чем за 10 000 замен и длина строки в процессе работы не превышает 1000. Выходные данные: в первой строке — строка, получившаяся после выполнения программы; во второй — количество выполненных замен. Пример. Входные данные:

2222211111
3
21 12
111 3
22 1

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

3312
29