捷克美食以 $$$n$$$ 开胃菜和 $$$n$$$ 主菜为特色。第 $$$i$$$ 开胃菜的辣度为 $$$a_i$$$,第 $$$i$$$ 主菜的辣度为 $$$b_i$$$。
典型的捷克餐仅由一份开胃菜和一份主菜组成。您希望将 $$$n$$$ 开胃菜和 $$$n$$$ 主菜配对为 $$$n$$$ 餐食,并且每份开胃菜和每份主菜都包含在一顿饭中。
您的饭菜应该给食客带来惊喜,因此您希望同一顿饭的两部分的辣度尽可能不同。一顿饭的魅力就在于开胃菜的辣度和主菜辣度的差异(绝对值)。所以,由辣度为$$$x$$$的开胃菜和辣度为$$$y$$$的主菜组成的一餐,其魅力等于$$$|x-y|$$$。
您想要最大限度地发挥由此产生的 $$$n$$$ 餐点的最低魅力。你所能达到的最小魅力的最大可能值是多少?
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1\,000$$$)——测试用例的数量。 $$$t$$$ 测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5\,000$$$) – 开胃菜和主菜的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{9}$$$) — $$$n$$$ 开胃菜的辣度。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \leq 10^{9}$$$) — $$$n$$$ 主菜的辣度。
保证所有测试用例的$$$n^2$$$总和不超过$$$25\cdot 10^6$$$。
输出
对于每个测试用例,打印您可以实现的最小魅力的最大可能值。
示例
输入 #1
4 3 0 0 0 1000000000 1000000000 1000000000 5 1 2 3 4 5 1 2 3 4 5 6 0 0 0 100 100 100 100 100 100 0 0 0 7 14 25 62 74 86 95 12 51 62 71 72 92 20 84
输出 #1
1000000000 2 100 30
注意
在第一个测试用例中,无论你如何搭配前菜和主菜,每顿饭都会有一份辣度为$$$0$$$的前菜和一份辣度为$$$1000000000$$$的主菜,所以每顿饭的魅力都是$$$1000000000$$$。
在第二个测试用例中,搭配开胃菜和主菜的一种最佳方式是:$$$(1, 5)$$$、$$$(2, 4)$$$、$$$(3, 1)$$$、$$$(4, 2)$$$、$$$(5, 3)$$$。相应的餐点有魅力:$$$4$$$、$$$2$$$、$$$2$$$、$$$2$$$、$$$2$$$。由此产生的最低魅力是 $$$2$$$。
在第三个测试用例中,最大化最小魅力的一种方法是将三道辣度$$$0$$$的开胃菜与三道辣度$$$100$$$的主菜配对,并将三道辣度$$$100$$$的开胃菜与三道辣度$$$0$$$的主菜配对。这样做,每顿饭的魅力就正好是$$$100$$$。