== include(page="template/taskheader" task_id="farmerj") ==

Rob Kolstad este suparat Farmer John si vacile sale, datorita greutatilor intampinate de echipa USACO in ultima vreme (bani putini, probleme furate, etc). Fiind superstitios, el crede ca problemele se trag de la numele lui Farmer John. De aceea, el doreste sa ii schimbe acestuia numele. Pentru a realiza acest lucru, Rob are la dispozitie un sir de celmult 50 de caractere. El vrea sa obtina $2$ siruri de caractere care sa formeze noul nume al lui Farmer John si care sa aiba urmatoarea proprietate: trebuie sa existe o posibilitate de a interclasa cele $2$ siruri astfel incat sirul obtinut sa fie un subsir al sirului pe care il are la dispozitie Rob (atentie! *subsir* este diferit de *subsecventa*). In afara de aceasta conditie, cele $2$ siruri trebuie sa satisface niste criterii de usurinta a pronuntarii. Mai exact, exista $M$ perechi de caractere care nu pot aparea unul dupa celalalt in nici unul din cele $2$ nume.

Rob Kolstad este suparat pe Farmer John si vacile sale, datorita greutatilor intampinate de echipa USACO in ultima vreme (bani putini, probleme furate, etc). Fiind superstitios, el crede ca problemele se trag de la numele lui Farmer John. De aceea, el doreste sa ii schimbe acestuia numele. Pentru a realiza acest lucru, Rob are la dispozitie un sir $S$. El vrea sa obtina $2$ siruri de caractere care sa formeze noul nume al lui Farmer John si care sa aiba urmatoarele proprietati:
 
* trebuie sa existe o posibilitate de a interclasa cele $2$ siruri astfel incat sirul obtinut sa fie un subsir al sirului $S$ (atentie! *subsir* este diferit de *subsecventa*).
* suma lungimilor celor $2$ siruri sa fie maxima
 
In afara de aceste conditii, cele $2$ siruri trebuie sa satisfaca niste criterii de usurinta a pronuntarii. Mai exact, exista $M$ perechi de caractere care nu pot aparea unul dupa celalalt in nici unul din cele $2$ nume.

h2. Date de intrare

...

Pe prima linie a fisierului de intrare $farmerj.in$ se afla sirul de caractere $S$ pe care il are Rob la dispozitie. Pe a doua linie se afla numarul intreg $M$. Urmatoarele $M$ linii contin cate $2$ caractere alfanumerice care nu pot aparea unul dupa altul in nici unul din cele $2$ nume.

h2. Date de iesire

...

In fisierul de iesire $farmerj.out$ veti afisa 2 linii. A $i$-a din cele 2 linii va contine pozitiile din cadrul sirului $S$ pe care se afla caracterele ce compun al $i$-lea nume. Aceste pozitii trebuie afisate in ordine crescatoare.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1$ ≤ lungimea sirului $S$ ≤ $50$
* Sirul $S$ este alcatuit numai din caractere alfanumerice.
* In mod evident, caracterul de pe orice pozitie $i$ a lui $S$ poate apartine doar unuia din cele $2$ nume.
* Oricare din cele $2$ nume poate contine $0$ caractere.

h2. Exemplu

h2. Exemple

table(example). |_. farmerj.in |_. farmerj.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicatie
 
...

| FJOHNARMERZ
14
FJ
FO
FH
FN
ZF
ZJ
ZO
ZH
ZN
ZA
ZR
ZM
ZE
ZR
| 1 6 7 8 9 10
2 3 4 5
|
| 123456789
5
81
84
89
56
68
| 1 2 3 4 5 9
6 7 8
|
| 1223
2
22
23
| 1 2
4
|

== include(page="template/taskfooter" task_id="farmerj") ==

2150