admitere

Să ne imaginăm faptul că la un anumit liceu există doar două clase per generație: una de Real și una de Uman. În prezent au loc înscrierile pentru clasa a IX-a. Cele două clase au fiecare câte $M$ locuri disponibile, atât la Real, cât şi la Uman. Dacă lista de elevi înscriși la o anumită clasă conține mai mult de $M$ elevi, vor fi admiși acei $M$ elevi care au notele cele mai mari. Ambele clase au deja $M$ elevi înscriși, iar pentru fiecare se știe nota cu care a fost înscris la clasa respectivă.

Mai există însă $N$ elevi, singurii încă neînscriși, care sunt privilegiați în acest proces (fiindcă au terminat gimnaziul la acest liceu). Privilegiul lor constă în următorul fapt: ei se pot înscrie acum, după ce înscrierile publice au fost încheiate, și se cunosc notele de înscriere la ambele clase. Fiecare din cei $N$ elevi are câte două note: nota cu care ar fi înscris la Real și nota cu care ar fi înscris la Uman (acestea pot fi diferite, deoarece examenele de admitere de la cele două clase diferă). Fiecare din cei $N$ elevi va alege să se înscrie în maxim o clasă. Ei își vor coordona alegerile astfel încât să maximizeze numărul de elevi admiși. Deoarece calculele devin destul de complicate, aceștia s-ar putea folosi de ajutorul vostru.

Cerinţe

Cei $N$ elevi doresc răspunsul la următoarele două întrebări:

1. Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă se pune restricția suplimentară ca toți elevii privilegiați admiși să fie admiși la aceeași clasă?
2. Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă aceștia se pot înscrie la clase diferite?

Date de intrare

Fişierul de intrare admitere.in conţine pe primul rând o valoare egală cu $1$ sau $2$, reprezentând cerința ce urmează a fi rezolvată. Următoarea linie conține cele două numere $N$ și $M$. Pe al treilea rând se află $M$ numere, separate prin câte un spaţiu, reprezentând notele cu care au fost înscriși elevii care formează momentan clasa de Real. Pe al patrulea rând se află $M$ numere, separate prin câte un spaţiu, reprezentând notele cu care au fost înscriși elevii care formează momentan clasa de Uman. Următoarele $N$ linii vor conține câte o pereche de numere $R_i$ și $U_i$, separate prin câte un spaţiu, reprezentând nota cu care al $i$-lea elev privilegiat s-ar înscrie la clasa de Real, respectiv la clasa de Uman.

Date de ieşire

Fișierul de ieșire admitere.out va conține pe prima linie valoarea $MAX$: numărul maxim de elevi privilegiaţi admiși. A doua linie va conține un șir de $N$ caractere din mulțimea $\{$R$,$ U$,$ X$\}$, care va descrie scenariul optim. Dacă al $i$-lea elev va fi înscris la Real, al $i$-lea caracter va fi egal cu R. Dacă al $i$-lea elev va fi înscris la Uman, al $i$-lea caracter va fi egal cu U. Dacă acesta nu va fi înscris nicăieri, al $i$-lea caracter va fi egal cu X.

Deoarece elevii nu vor să depună efort inutil, un elev privilegiat care nu va fi admis în scenariul optim nu se va înscrie la nicio clasă. Cu alte cuvinte, pentru ca scenariul descris să fie considerat corect este necesar ca exact $MAX$ caractere din șir să fie diferite de X.

Restricţii şi precizări

• $1 \leq N, M \leq 2\ 000$
• Teste în valoare totală de 25 de puncte vor solicita rezolvarea cerinței 1, iar restul de 65 de puncte vor solicita rezolvarea cerinței 2. Din oficiu sunt acordate 10 puncte.
• Pentru cerința 2, teste în valoare totală de 45 de puncte vor avea $1 \leq N, M \leq 150$.
• Toate cele $N + M$ note pentru clasa de Real sunt distincte două câte două. Același lucru este valabil și în cazul notelor pentru clasa de Uman.
• Toate notele sunt numere naturale din intervalul $[1, 4\ 000]$.
• Notele elevilor deja înscriși de la clasa de Real, respectiv Uman vor fi date în ordine crescătoare.
• În cazul în care există mai multe soluții corecte, este acceptată oricare dintre acestea.

Exemplul 1

admitere.in

1
2 3
2 4 6
6 7 8
3 5
12 14

admitere.out

1
XR

Explicație

Nu este posibil ca ambii elevi să fie admiși la aceeași clasă. Există mai multe soluții în care un singur elev este admis: XR, XU, RX. Oricare din acestea este corectă.

Exemplul 2

admitere.in

2
2 3
2 4 6
6 7 8
3 5
12 14

admitere.out

2
RU

Explicație

Deoarece acum rezolvăm cerința 2, ne este permis să înscriem elevii la clase diferite. Există o soluție în care ambii elevi sunt admiși, iar aceasta este unică: cea în care elevul $1$ este înscris la Real (el nu putea fi admis la Uman indiferent de decizia celui de-al doilea elev), iar elevul $2$ este înscris la Uman.