Qwerty se joacă foarte mult cu numere aleatoare. Recent şi-a combinat pasiunea pentru numere aleatoare cu pasiunea pentru permutări. Qwerty are un şir de numere distincte şi o permutare . El a început să aplice permutarea asupra şirului. Ar vrea să aplice permutarea de un număr infinit de ori asupra şirului, dar din cauză că lumea se va sfârşi în anul s-a gândit să-ţi ceară ajutorul ca să îşi satisfacă curiozitatea bolnavă.
Cerinţă
Qwerty te roagă să îi spui care este cel mai mic şir din punct de vedere lexicografic pe care îl poate obţine aplicând permutarea asupra şirului de un număr oarecare de ori şi în schimb îţi oferă de puncte şi o şansă în plus pentru IOI.
Date de intrare
Fişierul de intrare randomizare.in conţine pe prima linie numărul natural reprezentând lungimea permutării şi a şirului , pe a doua linie se vor afla numere naturale distincte reprezentând elementele şirului , iar pe a treia linie se vor afla numere naturale distincte cuprinse între şi reprezentând elementele permutării .
Date de ieșire
În fişierul de ieşire randomizare.out se vor afişa numere naturale distincte reprezentând cel mai mic şir din puncte de vedere lexicografic ce poate fi obţinut.
Restricții și precizări
- Elementele şirului pot fi memorate în variabile de tip intreg, pe de biţi cu semn.
Exemplu
randomizare.in
10
18 5 67 25 4 68 34 65 74 82
4 3 8 7 1 5 2 10 6 9
randomizare.out
4 34 5 18 68 74 25 67 82 65
Explicație
Şirurile pe care le poate obţine Qwerty sunt: