Алиса и Боб играют в игру на матрице, состоящей из $$$2$$$ строк и $$$m$$$ столбцов. В ячейке в $$$i$$$-й строке в $$$j$$$-м столбце лежит $$$a_{i, j}$$$ монет.
Изначально Алиса и Боб стоят в ячейке $$$(1, 1)$$$. Они собираются пройти какой-то последовательностью ходов в ячейку $$$(2, m)$$$.
Возможные ходы следующие:
- Пойти направо — из некоторой ячейки $$$(x, y)$$$ в $$$(x, y + 1)$$$;
- Пойти вниз — из некоторой ячейки $$$(x, y)$$$ в $$$(x + 1, y)$$$.
Сначала Алиса делает все свои ходы, пока не достигнет $$$(2, m)$$$. Она собирает монеты во всех клетках, которые они посещает (включая стартовую).
Когда Алиса заканчивает, Боб начинает свой путь. Он также делает ходы, чтобы достичь $$$(2, m)$$$, и собирает монеты во всех клетках, которые он посетил, а Алиса нет.
Счет в игре равен суммарному количеству монет, которые собрал Боб.
Алиса хочет минимизировать счет. Боб хочет максимизировать счет. Какой будет счет в игре, если оба игрока играют оптимально?
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Затем следуют описания $$$t$$$ наборов входных данных.
В первой строке каждого набора записано одно целое число $$$m$$$ ($$$1 \le m \le 10^5$$$) — количество столбцов в матрице.
В $$$i$$$-й из следующих $$$2$$$ строк записаны $$$m$$$ целых чисел $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^4$$$) — количество монет в ячейке в $$$i$$$-м ряду в $$$j$$$-м столбце матрицы.
Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
На каждый набор входных данных выведите одно целое число — счет игры, если оба игрока играют оптимально.
3 3 1 3 7 3 5 1 3 1 3 9 3 5 1 1 4 7
7 8 0
Пути для наборов входных данных из примеров изображены ниже. Путь Алисы раскрашен красным, а путь Боба — синим.
