This page is still under construction.

Parts of this page are still being built. What you see may change.

Let's Play Curling

Time limit1sMemory limit512 MB

Summary
Given red and blue stone positions on a line, find a center point c that maximizes how many red stones are strictly closer to c than every blue stone, or report Impossible.
Level

Medium5 of 10

Topics
Sorting, Greedy, Math, Array
Solved
No attempts yet

Problem

Curling is a sport in which players slide stones on a sheet of ice toward a target area. The team with the nearest stone to the center of the target area wins the game.

Two teams, Red and Blue, are competing on the number axis. After the game there are (n+m)(n+m) stones remaining on the axis, nn of them for the Red team and the other mm of them for the Blue. The ii-th stone of the Red team is positioned at aia_i and the ii-th stone of the Blue team is positioned at bib_i.

Let cc be the position of the center of the target area. From the description above we know that if there exists some ii such that 1≤i≤n1 \le i \le n and for all 1≤j≤m1 \le j \le m we have ∣c−ai∣<∣c−bj∣|c - a_i| < |c - b_j| then Red wins the game. What's more, Red is declared to win pp points if the number of ii satisfying the constraint is exactly pp.

Given the positions of the stones for team Red and Blue, your task is to determine the position cc of the center of the target area so that Red wins the game and scores as much as possible. Note that cc can be any real number, not necessarily an integer.

Input

There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains two integers nn and mm (1≤n,m≤1051 \le n, m \le 10^5) indicating the number of stones for Red and the number of stones for Blue.

The second line contains nn integers a1,a2,⋯ ,ana_1, a_2, \cdots, a_n (1≤ai≤1091 \le a_i \le 10^9) indicating the positions of the stones for Red.

The third line contains mm integers b1,b2,⋯ ,bmb_1, b_2, \cdots, b_m (1≤bi≤1091 \le b_i \le 10^9) indicating the positions of the stones for Blue.

It's guaranteed that neither the sum of nn nor the sum of mm will exceed 5×1055 \times 10^5.

Output

For each test case output one line. If there exists some cc so that Red wins and scores as much as possible, output one integer indicating the maximum possible score of Red (NOT cc). Otherwise output "Impossible" (without quotes) instead.

Hint

For the first sample test case we can assign c=2.5c = 2.5 so that the stones at position 2 and 3 for Red will score.

For the second sample test case we can assign c=7c = 7 so that the stones at position 5 and 7 for Red will score.

Examples1

  1. Example 1

    Input
    3
    2 2
    2 3
    1 4
    6 5
    2 5 3 7 1 7
    3 4 3 1 10
    1 1
    7
    7
    
    Expected output
    2
    3
    Impossible