У Поликарпа есть любимая последовательность \(a[1 \dots n]\), которая состоит из \(n\) целых чисел. Он выписал ее на доску следующим образом:
- максимально слева (в начале доски) он написал число \(a_1\);
- максимально справа (в конце доски) он написал число \(a_2\);
- потом максимально слева (но правее, чем \(a_1\)) он написал число \(a_3\);
- потом максимально справа (но левее, чем \(a_2\)) он написал число \(a_4\);
- Поликарп продолжил действовать также, пока не выписал на доску всю последовательность.
Вот что будет изображено после четырёх действий (конечно, если \(n \ge 4\)). Например, если \(n=7\) и \(a=[3, 1, 4, 1, 5, 9, 2]\), то Поликарп выпишет на доску последовательность \([3, 4, 5, 2, 9, 1, 1]\).
Вы увидели последовательность на доске и теперь хотите узнать, какая была любимая последовательность Поликарпа.
Выходные данные
Выведите \(t\) ответов на наборы входных данных. Каждый ответ — это последовательность \(a\), которую Поликарп выписывал на доску.
Примечание
В первом наборе входных данных последовательность \(a\) совпадает с последовательностью из условия. Состояния доски после каждого шага выглядят так:
\([3] \Rightarrow [3, 1] \Rightarrow [3, 4, 1] \Rightarrow [3, 4, 1, 1] \Rightarrow [3, 4, 5, 1, 1] \Rightarrow [3, 4, 5, 9, 1, 1] \Rightarrow [3, 4, 5, 2, 9, 1, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
7
3 4 5 2 9 1 1
4
9 2 7 1
11
8 4 3 1 2 7 8 7 9 4 2
1
42
2
11 7
8
1 1 1 1 1 1 1 1
|
3 1 4 1 5 9 2
9 1 2 7
8 2 4 4 3 9 1 7 2 8 7
42
11 7
1 1 1 1 1 1 1 1
|