Fișierul intrare/ieșire	mostenire.in, mostenire.out	Sursă	ONI 2018 clasa a 5-a
Autor	Flavius Boian	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.3 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Moștenire (clasa a 5-a)

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,..., 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, ..., 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 si 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țe

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

• 1 ≤ N ≤ 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, ..., N
• 1 ≤ K ≤ 100
• pentru toate perechile de poziții modificate de rege: S ≤ 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.

Exemplu