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 nouă 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 și cele K secvențe de cifre care au fost modificate și le cere să găsească: 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ța

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 fișier 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 inițiale 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 ≤ 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 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

Exemplu 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 => Z=3, iar cifrele distincte care au ocupat succesiv această poziție sunt 3, 2, 1, 7. Aceste cifre se vor scrie în fișier în ordine crescătoare