H. Номын солилцоо

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сургуульд ном унших дуртай $n$ сурагч байна. Сурагч бүр яг нэг сайн найзтай ба сурагч бүр өөр яг нэг сурагчийн сайн найз байна. Сурагч бүр сонирхдог яг нэг нэг номтой.

Сурагчид хоорондоо номоо хуваалцхаар шийдсэн. Өдөр бүр бүх сурагч өөрийн номоо сайн найздаа өгнө. Иймд өдөр бүр сурагч бүр яг нэг номтой байна.

Таны ажил бол сайн найзуудын жагсаалтыг ашиглан $k$ өдрийн дараах сурагчдын номын солилцоог тодорхойлох юм. Хялбарчлахын тулд бүх сурагч 1-c $n$ хүртэл дугаарлагдсан.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($2 ≤ n ≤ 100000, 1 ≤ k ≤ 10^{16}$) байх буюу сурагчдын тоо болон тэдний ном солилцох өдрийн тоо юм.

Хоёр дахь мөрөнд ялгаатай $n$ бүхэл тоон утга $a_{i}$ ($1 ≤ a_{i} ≤ n$) байх ба энд $a_{i}$ нь $i$ дугаар бүхий сайн найзтай сурагчийн дугаар байна.

Ямар ч сурагч өөрийнхөө сайн найз биш гэдэг нь тодорхой.

Гаралт

Нэг мөрөнд ялгаатай $n$ бүхэл тоон утга хэвлэх ба энд $i$-р бүхэл тоон утга нь анх $i$ дугаартай сурагчид байсан номыг $k$ өдрийн дараа авах сурагчийн дугаар байна.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4 1
2 4 1 3
Гаралт
3 1 4 2 
Оролт
5 5
3 4 5 2 1
Гаралт
3 4 5 2 1 
Оролт
6 18
2 3 5 1 6 4
Гаралт
1 2 3 4 5 6 

Тэмдэглэл

Эхний жишээний тайлбарыг авч үзье.

Энд 4 сурагч ба 1 өдөр байна. Сайн найзуудын жагсаалт нь {2, 4, 1, 3}-тай тэнцүү. Энэ нь:

  • 3 дугаартай сурагч нь 1 дугаартай сурагчийн сайн найз
  • 1 дугаартай сурагч нь 2 дугаартай сурагчийн сайн найз
  • 4 дугаартай сурагч нь 3 дугаартай сурагчийн сайн найз
  • 2 дугаартай сурагч нь 4 дугаартай сурагчийн сайн найз гэсэн үг.

Эхний өдрийн дараа номын солилцоо нь {3, 1, 4, 2} болно.

  • 3 дугаартай сурагч анх 1 дугаартай сурагчид байсан номыг авна,
  • 1 дугаартай сурагч анх 2 дугаартай сурагчид байсан номыг авна,
  • 4 дугаартай сурагч анх 3 дугаартай сурагчид байсан номыг авна,
  • 2 дугаартай сурагч анх 4 дугаартай сурагчид байсан номыг авна.

Ингээд хариулт $3 1 4 2$ болно.

Сэтгэгдлүүдийг ачааллаж байна...