A92171.异或和
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
给定两个数组:长度为 n 的数组 a 和长度为 m 的数组 b。你可以进行任意多次如下操作:
- 选择 b 中的任意一个元素 bj,并将 所有 a 中的元素同时替换为 ai←ai∣bj(按位或)。
设数组 a 的异或和为 a1⊕a2⊕⋯⊕an(记号 ⊕ 表示按位异或)。
请你求出在进行若干次操作之后,数组 a 的异或和的最小值与最大值。
你可以进行 0 次或多次操作;也可以多次选择同一个 bj(再次选择对结果不再产生额外影响)。
输入格式
多组测试数据。
- 第一行一个整数 t(1≤t≤104),表示测试组数。
- 对于每组数据:
- 第一行两个整数 n,m(1≤n,m≤2×105)。
- 第二行 n 个整数 a1,a2,…,an。
- 第三行 m 个整数 b1,b2,…,bm。
保证所有测试数据中 n 的总和与 m 的总和均不超过 2×105。
元素范围:0≤ai,bi≤109。
输出格式
对于每组数据,输出一行两个整数,分别表示最小可能异或和与最大可能异或和。
输入输出样例
输入#1
2 2 3 0 1 1 2 3 3 1 1 1 2 1
输出#1
0 1 2 3
说明/提示
说明/提示
1≤t≤104,1≤n,m≤2×105,0≤ai,bi≤109。