mostenire

Regele Rufus dorește să stabilească moștenitorul averii sale, adică să ofere parola de la seif celui mai deștept dintre fiii săi. Inițial, regele a avut parola $X$ formată din $N$ cifre nenule și un cod cheie $Q$ (număr natural cu exact $9$ cifre, distincte, toate nenule). În fiecare an din cei $K$ ani de domnie, folosind codul cheie $Q$, Rufus a modificat câte o secvență de cifre din parolă ajungând la parola finală $P$.

Pentru fiecare secvență se cunoaște poziția $S$ a primei cifre din secvență și poziția $D$ a ultimei cifre din secvență. Astfel, secvența este formată din cifrele situate pe pozițiile $S$, $S+1$, $S+2$, $\dots$, $D$ în parola $X$.

Modificarea unei secvențe din $X$ constă în înlocuirea fiecărei apariții a cifrei $1$ cu prima cifră a lui $Q$, apoi a fiecărei apariții a cifrei $2$ cu a doua cifră a lui $Q$, $\dots$, a fiecărei apariții a cifrei $9$ cu ultima cifră a lui $Q$.

Pentru a decide moștenitorul, regele le dă fiilor parola finală $P$, codul cheie $Q$, numărul $K$ de ani de domnie și cele $K$ secvențe de cifre care au fost modificate și le cere să găsescă: parola inițială $X$, poziția minimă $Z$ din parola $X$ care a apărut în cele mai multe secvențe dintre cele modificate de rege de-a lungul celor $K$ ani de domnie și cifrele distincte care au ocupat poziția $Z$ în cei $K$ ani.

Cerință

Scrieţi un program care citește numerele $Q$, $N$, $K$, cele $N$ cifre ale parolei finale $P$ și cele $K$ perechi de poziții $S$ și $D$, și care rezolvă următoarele două cerinţe:

1. Determină parola inițială $X$;
2. Determină poziția minimă $Z$ și cifrele distincte care au ocupat această poziție în cei $K$ ani de domnie.

Date de intrare

Fișierul de intrare mostenire.in conține pe prima linie un număr natural $C$ reprezentând cerința din problemă care trebuie rezolvată ($1$ sau $2$).
A doua linie din fișier conține cele trei numere naturale $Q$, $N$ și $K$, separate prin câte un spațiu.
A treia linie din fisier conține cele $N$ cifre ale parolei finale $P$, separate prin câte un spațiu.
Fiecare linie dintre următoarele $K$, conține câte două numere naturale $S$ și $D$, separate printr-un singur spațiu, reprezentând câte o pereche de poziții.

Date de ieșire

Dacă $C=1$, fișierul de ieşire mostenire.out va conţine pe prima linie cele $N$ cifre ale parolei initiale $X$, separate prin câte un spațiu, în ordinea în care apar în $X$, reprezentând răspunsul la cerința $1$.

Dacă $C=2$, fișierul de ieşire mostenire.out va conţine pe prima linie numărul natural $Z$, iar pe a doua linie cifrele distincte care au apărut pe poziția minimă $Z$, reprezentând răspunsul la cerința $2$. Acestea vor fi afișate în ordine crescătoare, separate prin câte un spațiu.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$;
• Numărul natural $Q$ este format din exact $9$ cifre, distincte și nenule;
• Pozițiile cifrelor din parola $X$ sunt numerotate cu numerele distincte consecutive $1$, $2$, $\dots$, $N$;
• $1 \leq K \leq 100$;
• Pentru toate perechile de poziții modificate de rege: $S \leq D$;
• Cel puțin o cifră din parola $X$ va fi înlocuită;
• Pentru rezolvarea corectă a cerinţei $1$ se acordă $50$ de puncte;
• Pentru rezolvarea corectă a cerinței $2$ se acordă $50$ de puncte.

Exemplul 1

mostenire.in

1
712534698 12 4
1 4 7 1 3 4 7 1 4 8 1 8
2 4
6 11
3 9
1 7

mostenire.out

2 7 3 5 4 1 3 3 7 9 2 8

Explicație

Cerinţa este 1, N=12, K=4.

Exemplul 2

mostenire.in

2
712534698 12 4
1 4 7 1 3 4 7 1 4 8 1 8
2 4
6 11
3 9
1 7

mostenire.out

3
1 2 3 7

Explicație

Cerinţa este $2$, $N=12$, $K=4$.
$P=(1 \ 4 \ 7 \ 1 \ 3 \ 4 \ 7 \ 1 \ 4 \ 8 \ 1 \ 8)$
Pozițiile care au apărut în cele mai multe secvențe sunt: $3, 4, 6, 7 \rightarrow Z=3$, iar cifrele distincte care au ocupat succesiv această pozitie sunt $3, 2, 1, 7$. Aceste cifre se vor scrie în fișier în ordine crescătoare.