在二维平面上有 $n$ 条红线和 $n$ 条蓝线。第 $i$ 条红线的方程为 $y = a_i x + b_i$，第 $i$ 条蓝线的方程为 $x = c_i$。

定义将一条红线与一条蓝线配对的值为它们交点的 $y$ 坐标。你需要将每条红线与且仅与一条蓝线配对，从而得到 $n$ 个值。确定这些值可能的最大中位数。

长度为 $n$ 的数组的中位数是该数组中第 $\lceil \frac{n}{2} \rceil$ 大的元素。例如，数组 $[3, 4, 2]$ 的中位数是 $3$，数组 $[1, 1, 4, 5, 1, 4]$ 的中位数是 $4$。

输入格式

第一行包含测试用例的数量 $T$ ($1 \le T \le 10^5$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($-10^{18} \le b_i \le 10^{18}$)。

每个测试用例的第四行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($-10^9 \le c_i \le 10^9$)。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，即可能的最大中位数。

样例

输入 1

3
5
0 5 -2 1 2
9 -4 0 10 5
-4 -1 4 -2 4
10
-6 3 1 0 6 -2 -4 3 0 10
22 65 11 1 -34 -1 -39 -28 25 24
10 9 1 -2 -5 8 -7 -10 -7 -7
1
101
48763
651

输出 1

9
25
114514