Rezolvare PBinfo #143

Se dă o permutare P a mulțimii {1,2, … ,N}. Se mai dau Q întrebări specificate prin câte un număr D.

Cerință

Dacă D este pozitiv trebuie să determinăm a D-a permutare care succede lexicografic P iar dacă D este negativ, a D-a permutare care precede lexicografic P.

Date de intrare

Fișierul permutari3.in are pe prima linie un număr natural N. Pe linia a 2-a sunt N numere distincte din mulțimea {1,2, ... ,N}, separate prin câte un spațiu, reprezentând permutarea dată, P. Pe linia a 3-a este numărul Q. Pe următoarele Q linii se găsește câte un număr D cu semnificația de mai sus.

Date de ieșire

Fișierul permutari3.out conține Q linii. Pe fiecare linie este un șir de N numere, distincte, din mulțimea {1,2, ... ,N}, reprezentând răspunsul la o întrebare, în ordinea în care acestea apar în fișierul de intrare.

Restricții

• 3 ≤ N ≤ 15
• 1 ≤ Q ≤ 10000
• valorile D indică o permutare validă;
• șirul a1, a2, ..., an precede lexicografic șirul b1, b2, ..., bn dacă există o poziție k așa încât ak < bk și ai = bi pentru orice i de la 1 la k-1;
• pentru 30% dintre teste, N<=6;
• pentru 20% dintre teste, se garantează că toate valorile D sunt pozitive.

Exemplu

permutari3.in

4
2 1 4 3
2
1
-2

permutari3.out

2 3 1 4 
1 4 3 2

Explicaţie

Permutarea 2 3 1 4 urmează lexicografic imediat după permutarea 2 1 4 3.

Înaintea permutării 2 1 4 3 se află permutarea 2 1 3 4 şi apoi permutarea 1 4 3 2.