题目描述
阿历克斯附体的希尔芬、崩巴附体的切绘、蒸汽姬海老名与全能少女小埋在游乐场玩旋转咖啡杯。双鱼座的切绘占卜得到的幸运数字是 3,然而在游乐场却没有编号为 3 的旋转咖啡杯。全能少女小埋想到了办法,旋转咖啡杯的编号构成了一个整数集合,小埋也给出了一个整数集合,并定义了一个操作。现在,她想知道操作后的旋转咖啡杯编号的最低位之和是多少,如果是 3,那么她就可以带着切绘去坐旋转咖啡杯啦!
(以上内容与题目内容无必然联系)
有两个非负整数组成的可重集合 A 和 B。
现在你可以对 A 中至多 k 个元素进行操作。操作方法为:设你准备操作且未被操作过的 A 中的元素是 a,你可以在 B 中选取任意一个元素 b,将 a 修改为 a⊕b(这里 ⊕ 表示二进制按位异或),然后从 B 中删去 b。
最终,你要使 A 中所有元素的 lowbit 之和最小。正整数的 lowbit 定义为其二进制最低非零位的值,0 的 lowbit 规定为 0,例如 lowbit(0)=0,lowbit(1)=1,lowbit(24)=8。形式化地有:
lowbit(x)={max({2k:k∈N,2k∣x})0x∈N+x=0
(其中 ∣ 表示整除)
你需要求出操作后 A 中所有元素的 lowbit 之和的可能的最小值。
输入格式
第一行一个整数 n 表示 A 的元素个数。
接下来一行 n 个整数 {ai} 表示 A 中元素。
接下来一行一个整数 m 表示 B 的元素个数。
接下来一行 m 个整数 {bi} 表示 B 中元素。
接下来一行一个整数 k。
输出格式
输出一行一个整数 S 表示操作后 A 中所有元素的 lowbit 之和的可能的最小值。
样例
5
6 18 14 1 13
5
7 7 8 8 15
3
5
{6,18,14,1,13} 的 lowbit 分别为 2,2,2,1,1,将 6,18,14 分别与 7,7,15 操作,得到新集合为 {1,21,1,1,13},其 lowbit 分别为 1,1,1,1,1,答案为 5。
数据范围与提示
对于所有数据,1≤n,m,k≤1.2×106,0≤ai,bi≤109。
Subtask # |
分值 |
n,m |
k |
特殊性质 |
1 |
6 |
1≤n,m≤8 |
1≤k≤8 |
无 |
2 |
8 |
1≤n,m≤106 |
k=1 |
没有元素同时在 A,B 中出现 |
3 |
10 |
无 |
4 |
9 |
1≤n,m≤500 |
1≤k≤500 |
没有元素同时在 A,B 中出现 |
5 |
11 |
无 |
6 |
9 |
1≤n,m≤106 |
1≤k≤106 |
B 中元素均相等 |
7 |
13 |
1≤n,m≤5×103 |
1≤k≤5×103 |
无 |
8 |
15 |
1≤n,m≤3×105 |
1≤k≤3×105 |
9 |
19 |
1≤n,m≤1.2×106 |
1≤k≤1.2×106 |