A92171.异或和

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给定两个数组:长度为 nn 的数组 aa 和长度为 mm 的数组 bb。你可以进行任意多次如下操作:

  • 选择 bb 中的任意一个元素 bjb_j,并将 所有 aa 中的元素同时替换为 aiai    bja_i \leftarrow a_i \;|\; b_j(按位或)。

设数组 aa异或和a1a2ana_1 \oplus a_2 \oplus \cdots \oplus a_n(记号 \oplus 表示按位异或)。
请你求出在进行若干次操作之后,数组 aa 的异或和的最小值最大值

你可以进行 00 次或多次操作;也可以多次选择同一个 bjb_j(再次选择对结果不再产生额外影响)。

输入格式

多组测试数据。

  • 第一行一个整数 tt1t1041 \le t \le 10^4),表示测试组数。
  • 对于每组数据:
    • 第一行两个整数 n,mn,m1n,m2×1051 \le n,m \le 2\times 10^5)。
    • 第二行 nn 个整数 a1,a2,,ana_1,a_2,\ldots,a_n
    • 第三行 mm 个整数 b1,b2,,bmb_1,b_2,\ldots,b_m

保证所有测试数据中 nn 的总和与 mm 的总和均不超过 2×1052\times 10^5
元素范围:0ai,bi1090 \le a_i,b_i \le 10^9

输出格式

对于每组数据,输出一行两个整数,分别表示最小可能异或和最大可能异或和

输入输出样例

  • 输入#1

    2
    2 3
    0 1
    1 2 3
    3 1
    1 1 2
    1

    输出#1

    0 1
    2 3

说明/提示

说明/提示

1t1041 \leq t \leq 10^41n,m2×1051 \leq n, m \leq 2 \times 10^50ai,bi1090 \leq a_i, b_i \leq 10^9

首页