Chalga
НОИ 2019, Контрола 3
Time Limit: 0.6s, Memory Limit: 256MiB
Независимо от музикалните си предпочитания, всеки човек в България рано или късно се сблъсква с нещото, наречено "чалга".
Макар и силно отблъсната от отчаяните опити на изпълнителите да докарат някой верен тон в нещото, което поради липса на друга дума ще наречем "песен", Ели не можеше да не признае, че авторите й бяха проявили известна доза креативност поне за клипа. Набор от N девойки (явно с гореща кръв, съдейки по оскъдното им облекло) танцуваха на N платформи, като всяка секунда сменяха платформата си, скачайки от една на друга. Момичето от платформа i отиваше на платформа Pi, като числата P1, P2, ..., PN образуваха пермутация - тоест след всяка секунда отново на всяка платформа имаше по точно една танцьорка. Забележителното беше, че песента имаше такава дължина K, че в края й всяка от танцьорките беше на началната си позиция! Така канали като πнер можеха да въртят една и съща песен отново и отново без видимо накъсване на видеото!
Елеонора беше запомнила част от "хореографията", но за съжаление не помнеше изцяло как танцьорките скачаха от платформа на платформа. Можете ли да ѝ помогнете, като допълните пермутацията на числата от 1 до N, която помни момичето, по такъв начин, че след K секунди всяка от танцьорките да бъде на началното си място?
Макар и силно отблъсната от отчаяните опити на изпълнителите да докарат някой верен тон в нещото, което поради липса на друга дума ще наречем "песен", Ели не можеше да не признае, че авторите й бяха проявили известна доза креативност поне за клипа. Набор от N девойки (явно с гореща кръв, съдейки по оскъдното им облекло) танцуваха на N платформи, като всяка секунда сменяха платформата си, скачайки от една на друга. Момичето от платформа i отиваше на платформа Pi, като числата P1, P2, ..., PN образуваха пермутация - тоест след всяка секунда отново на всяка платформа имаше по точно една танцьорка. Забележителното беше, че песента имаше такава дължина K, че в края й всяка от танцьорките беше на началната си позиция! Така канали като πнер можеха да въртят една и съща песен отново и отново без видимо накъсване на видеото!
Елеонора беше запомнила част от "хореографията", но за съжаление не помнеше изцяло как танцьорките скачаха от платформа на платформа. Можете ли да ѝ помогнете, като допълните пермутацията на числата от 1 до N, която помни момичето, по такъв начин, че след K секунди всяка от танцьорките да бъде на началното си място?
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K - съответно броят платформи и продължителността на песента в секунди. На втория ред ще бъдат зададени N цели числа P1, P2, ..., PN, задаващи частично пермутация. Позициите, за които Ели не помни къде отиват танцьорките, ще бъдат отбелязани с нули.
Изход
На стандартния изход изведете P1, P2, ..., PN, като нулите са заменени с числа между 1 и N, така че да се образува пермутация, при която след K секунди танцьорките отново да са на началните си позиции. Ако съществува повече от едно решение, изведете което и да е от тях.
Ограничения
- 1 ≤ N ≤ 50
- 0 ≤ Pi ≤ N
- 1 ≤ K ≤ 1,000,000,000
Примерен Вход | Примерен Изход |
---|---|
11 42 0 0 9 10 6 1 3 0 11 2 0 | 7 4 9 10 6 1 3 8 11 2 5 |
Ако номерираме танцьорките (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), то след първата секунда редът им ще е (6, 10, 7, 2, 11, 5, 1, 8, 3, 4, 9), след втората ще бъде (5, 4, 1, 10, 9, 11, 6, 8, 7, 2, 3) и т.н., като на 42-рата ще e отново (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11).
Забележете, че даденият отговор достига първоначалния си вид още на 21-вата секунда, но е в него и на 42-рата.
Друг възможен отговор за този вход би бил (5, 7, 9, 10, 6, 1, 3, 8, 11, 2, 4).
Друг възможен отговор за този вход би бил (5, 7, 9, 10, 6, 1, 3, 8, 11, 2, 4).