Наступает решающая битва за Хогвартс. Все \(n\) его обитателей собрались в холле для отражения атак противника. Каждый защитник Хогвартса обладает магической силой, которая представляет собой натуральное число от \(1\) до \(n\). Магические силы всех защитников различны.

Гарри решил, что строй защитников лучше всего отразит атаку, если магическая сила выстроившихся бойцов будет возрастать слева направо. Но бойцы уже выстроились в строй, для которого это условие, возможно, не выполняется.

Для того, чтобы отразить атаку, Гарри хочет переставить бойцов по возрастанию магической силы. Для этого он действует по следующему алгоритму. Гарри идет слева направо и смотрит на все пары бойцов, стоящих рядом. Если он чувствует, что левый боец сильнее правого, он меняет их местами.

Из предмета <<Основы маггловской информатики>> Гарри знает, что если он сделает \(n-1\) такой проход, все бойцы окажутся расположены в порядке возрастания их магической силы. Однако времени мало, поэтому Гарри успеет сделать только \(k\) таких проходов.

Помогите Гарри узнать, в каком порядке бойцы встретят армию противника.

2 1
1 2

1 2

3 1
2 3 1

2 1 3