#P9633. [ICPC 2020 Nanjing R] Let's Play Curling

[ICPC 2020 Nanjing R] Let's Play Curling

Description

[ICPC2020 Nanjing R] Let's Play Curling

红队和蓝队在冰面上向目标区域滑动冰壶,距离目标区域中心最近的队伍获胜。

两支队伍在一条直线上竞争。比赛结束后,有 (n+m)(n+m) 个冰壶在直线上, nn 个是红队的,剩下 mm 个是蓝队的。 红队的第 ii 个冰壶被放在 aia_i ,蓝队的第 ii 个冰壶被放在 bib_i

cc 是中心。如果存在一些 ii 使得 1in1 \le i \le n 并且对于所有 1jm1 \le j \le m 都有 cai<cbj|c - a_i| < |c - b_j| 红队就赢得比赛。另外,如果满足条件的 ii 的数目是 pp ,则认为红队赢得 pp 分。

给你红蓝两队的冰壶的位置,请你确定中心 cc 的值,使红队得分最多。注意, cc 是任意实数,不一定是整数。

Input Format

有很多测试样例。第一行输入一个整数 TT ,表示样例数量。对于每个测试样列:

第一行包括两个整数 nnmm (1n,m1051 \le n, m \le 10^5) 分别表示红队和蓝队的冰壶数量。

第二行包括 nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n (1ai1091 \le a_i \le 10^9) 表示红队的冰壶的位置。

第三行包括 mm 个整数 b1,b2,,bmb_1, b_2, \cdots, b_m (1bi1091 \le b_i \le 10^9)表示蓝队的冰壶的位置。

数据保证 nn 的总和以及 mm 的总和都不会超过 5×1055 \times 10^5

Output Format

每一个测试样列输出一行。如果存在 cc 使得红队获胜且得分最多, 输出一个整数表示红队最大  得分 \textbf{ 得分 } (不是 cc) 。否则输出 Impossible ( 不带引号 ) 。

样例 #1

样例输入 #1

3
2 2
2 3
1 4
6 5
2 5 3 7 1 7
3 4 3 1 10
1 1
7
7

样例输出 #1

2
3
Impossible
3
2 2
2 3
1 4
6 5
2 5 3 7 1 7
3 4 3 1 10
1 1
7
7
2
3
Impossible

Hint

对于第一个样例,当 c=2.5c = 2.5 时,红队的位于 2 和 3 的冰壶可以得分。

对于第二个样例,当 c=7c = 7 时,红队的位于 5 和 7 的冰壶可以得分。