A. Любимая последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть любимая последовательность $$$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$$$ ($$$1 \le t \le 300$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных находится целое число $$$n$$$ ($$$1 \le n \le 300$$$) — длина последовательности, записанной на доске.

В следующей строке находятся $$$n$$$ целых чисел $$$b_1, b_2,\ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — последовательность на доске.

Выходные данные

Выведите $$$t$$$ ответов на наборы входных данных. Каждый ответ — это последовательность $$$a$$$, которую Поликарп выписывал на доску.

Пример
Входные данные
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
Примечание

В первом наборе входных данных последовательность $$$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]$$$.