돔 구장

어느 야구팀이 돔 구장 건설을 계획하고 있다. 도시는 하나의 도로를 따라 일직선으로 늘어선 $N$개의 마을로 이루어져 있고, 각 마을은 x축 위의 서로 다른 정수 좌표에 위치한다. 설문을 통해 각 마을에 사는 야구 팬의 수를 이미 알고 있다.

팀은 모든 팬이 구장까지 이동하는 거리의 총합이 가장 작아지도록 어느 한 마을에 구장을 세우려 한다. 팬이 $f$명 있고 구장과의 거리가 $d$인 마을은 이 총합에 $f \times d$만큼 기여한다. 즉 마을의 좌표를 $x_i$, 구장을 세울 좌표를 $p$라 하면, 거리의 총합은 모든 마을에 대한 $f_i \times |x_i - p|$의 합이다.

예를 들어 좌표가 $(1, 2, 5, 7, 8)$인 마을 5개에 팬 수가 각각 $(3, 2, 4, 3, 1)$이라면, x좌표 $5$인 마을에 구장을 지을 때 모든 팬으로부터의 거리의 총합이 최소가 된다.

모든 팬으로부터의 거리의 총합을 최소로 만드는 마을의 좌표를 구하는 프로그램을 작성하라. 구장은 반드시 마을 중 한 곳에 지어야 하며, 모든 마을은 정수 x좌표 위에 있다.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

• 첫째 줄에 마을의 수 $N$ ($1 < N \le 100000$)이 주어진다.
• 둘째 줄에 마을들의 x좌표 $N$개가 오름차순으로 주어진다. 각 좌표는 $1$ 이상 $100000000$ 이하이다.
• 셋째 줄에 각 마을의 팬 수 $N$개가 주어진다. 각 값은 $1$ 이상 $10000$ 이하의 양의 정수이다.

표준 출력으로 출력한다. 각 테스트 케이스마다 정확히 한 줄에 정수 하나를 출력한다. 이 정수는 모든 팬으로부터의 거리의 총합을 최소로 만드는 마을의 좌표이다. 최솟값을 만드는 마을이 여러 개라면 그중 가장 작은 좌표를 출력한다.