Вам задана массив \(a\) длины \(n\), состоящий из нулей. Вы выполняете \(n\) действий с этим массивом: в течение \(i\)-го действия происходит следующая последовательность операций:
- Выбирается максимальный по длине подмассив (последовательный подотрезок), состоящий только из нулей, среди всех таких отрезков выбирается самый левый;
- Пусть этот отрезок равен \([l; r]\). Если \(r-l+1\) нечетно (не делится на \(2\)), то присваивается \(a[\frac{l+r}{2}] := i\) (где \(i\) — номер текущего действия), иначе (если \(r-l+1\) четно) присваивается \(a[\frac{l+r-1}{2}] := i\).
Рассмотрим массив \(a\) длины \(5\) (изачально \(a=[0, 0, 0, 0, 0]\)). Тогда он меняется следующим образом:
- Сначала мы выбираем отрезок \([1; 5]\) и присваиваем \(a[3] := 1\), таким образом \(a\) становится равен \([0, 0, 1, 0, 0]\);
- затем мы выбираем отрезок \([1; 2]\) и присваиваем \(a[1] := 2\), таким образом \(a\) становится равен \([2, 0, 1, 0, 0]\);
- затем мы выбираем отрезок \([4; 5]\) и присваиваем \(a[4] := 3\), таким образом \(a\) становится равен \([2, 0, 1, 3, 0]\);
- затем мы выбираем отрезок \([2; 2]\) и присваиваем \(a[2] := 4\), таким образом \(a\) становится равен \([2, 4, 1, 3, 0]\);
- и наконец мы выбираем отрезок \([5; 5]\) и присваиваем \(a[5] := 5\), таким образом \(a\) становится равен \([2, 4, 1, 3, 5]\).
Ваша задача — найти массив \(a\) длины \(n\) после выполнения всех \(n\) действий. Заметьте, что ответ существует и единственен.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ — массив \(a\) длины \(n\) после выполнения \(n\) действий, описанных в условии задачи. Заметьте, что ответ существует и единственен.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
2
3
4
5
6
|
1
1 2
2 1 3
3 1 2 4
2 4 1 3 5
3 4 1 5 2 6
|