CF1816B Grid Reconstruction

在一个 $2×n$ 的网格中 （$n$ 为偶数），标记 $1,2,\ldots,2n$，但每个数只能被使用 $1$ 次。 某条路径是从 $(1,1)$ 开始的单元序列，随后不断地向下走或向右走，直到到达 $(2,n)$。注意：这条路径不能超出网格的边界。 通过这条路径的成本是这条路径所通过的单元格上的数字交替和，即，设路径上的数为 $a,a_1,a_2,\ldots,a_k$（它是第几个被标记到的，它的下标就是几），则通过这条路径的成本就是 $ a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1} $。 你需要求一个在网格中标记 $1,2,...,2n$ 的方案，最大化成本最小的路径的成本。如果有多个答案，你可以输出任意一个。本题中，每个测试点包含 $t$ 组数据。

第一行包含 $t$（$t$ 是测试数据组数）。 随后的 $t$ 行，每行给出一个 $n$，表示网格的边长。 数据保证 $n\le10^5$。

共 $2t$ 行，每组测试数据两行，每行包含 $n$ 个整数，表示所需的网格。如果有多个答案，你可以输出任意一个。

在第一组测试数据中，只有两条从 $(1,1)$ 到 $(2,2)$ 的路径，它们的成本分别是 $3-1+4=6$ 和 $3-2+4=5$，其中成本更小的方案是 $5$，这是最优的方案。 在第二组测试数据中，有四条从 $(1,1)$ 到 $(2,4)$ 的路径，它们的成本分别是 $8-1+5-3+7=16$，$8-2+5-3+7=15$，$8-2+6-3+7=16$ 和 $8-2+6-4+7=15$，其中成本最小的一种方案是 $15$，这是最优的方案。