Transformacions de paraules P19888

Feu un programa que modifiqui (com a molt) $r$ vegades una paraula inicial $p$ usant unes quantes trasformacions $a \to b$. Cada transformació indica que si $p$ conté la subparaula $a$, llavors $a$ es pot substituir per $b$.

Entrada

L’entrada comença amb la paraula $p$. A continuació ve un nombre $n \ge 1$, seguit de $n$ parells de paraules $a$ i $b$ (diferents i de la mateixa longitud). L’entrada acaba amb un natural $r \ge 1$. Les paraules de cada parell mai no són més llargues que $p$.

Sortida

Escriviu els resultats d’aplicar $r$ vegades la primera de les transformacions donades que sigui possible en cada moment. Si la mateixa transformació es pot aplicar a més d’una posició, escolliu la de més a l’esquerra. El programa ha de deixar d’escriure si en algun moment no pot aplicar cap transformació més.