Kāršu jaukšana

Uzdevums

Alisei un Robertam ir kāršu kava ar N kārtīm, kuras numurētas ar naturāliem skaitļiem no 1 līdz N tā, ka nav divu kāršu ar vienādiem numuriem. N ir nepāra skaitlis. Bez tam Aliksei un Robertam ir arī kāršu kavas jaukšanas mašīna.

Kāršu kavas jaukšanas mašīna var sajaukt jebkuru kāršu kavu (kārtis tajā var būt patvaļīgā secībā), veicot dubultās sajaukšanas operāciju: visām pozīcijām i, 1<=i<=N, ja kārts i-tajā pozīcijā ir j un kārts j-tajā pozīcijā ir k, tad pēc kavas sajaukšanas i-tajā pozīcijā būs kārts k.

Alise un Roberts spēlē spēli. Alise vispirms uzraksta visus skaitļus no 1 līdz N patvaļīgā secībā a₁,a₂,....,a_N. Tad viņa saliek kārtis tā, ka a_i-tajā pozīcijā ir kārts ar numuru a_i+1 visiem i:1<=i<=N-1, bet a_N-tajā pozīcijā ir kārts ar numuru a₁.

Tādējādi, kārtis ir saliktas secībā x₁,x₂,....,x_N, kur x_i ir kārts i-tajā pozīcijā.

Pēc tam Alise pēc kārtas veic S dubultās sajaukšanas operācijas lietojot augstāk aprakstīto kāršu kavas jaukšanas mašīnu. Jaukšanas rezultātā kārtis kavā ir secībā p₁,p₂,....,p_N. Šo kavu Alise iedod Robertam un pasaka viņam arī skaitli S. Roberta uzdevums ir noteikt kāršu secību x₁,x₂,....,x_N kādā Alise bija kārtis salikusi sākumā pirms jaukšanas mašīnas izmantošanas.

Ievaddati

Teksta faila kartis.in pirmā rinda satur divus naturālu skaitļu N(1<=N<=1000) un S(1<=S<=1000) vērtības, kas atdalītas ar tukšumsimbolu.
Nākošajās N faila rindas apraksta kāršu kārtību kavā pēc jaukšanas mašīnas izmantošanas. Faila i+1-ajā rindā ir dota skaitļa p_i (skaitļa, kas atrodas i-tajā vietā pēc visām dubultās jaukšanas operācijām) vērtība.

Izvaddati

Teksta failam kartis.out jāsatur tieši N rindas un jāapraksta kāršu secība kavā pirms Alise izmantoja jaukšanas mašīnu.

Katram i, 1<=i<=N faila i-tajā rindā jābūt skaitļa x_i (skaitļa, kas atrodas i-tajā vietā pirms visām dubultās jaukšanas operācijām) vērtībai .

Piemērs

kartis.in	kartis.out
5 2 4 1 5 3 2	2 5 4 1 3
kartis.in	kartis.out
7 4 6 3 1 2 4 7 5	4 7 5 6 1 2 3

Atsauces