You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Csvoner 有两组无符号整数。

第一组有 $n$ 个数 $a_1\sim a_n$。第二组有 $m$ 个数 $b_1\sim b_m$。

我们要在第二组里找这样的数：用这个数和第一组里的每个数做按位与运算，算出来的结果还都是第一组里的那个数。现在问第二组里有几个这样的数呢？

形式化的说，求有多少个 $b_i(1\le i\le m)$，满足“对于任意的 $1\sim n$ 之内的 $j$，有 $b_i\&a_j=a_j$”

什么是按位与运算：即两个数在二进制下每一位都进行与运算组合出来的结果，比如 $(1010)_2 \& (1100)_2 = (1000)_2$，在 C++ 中，可以用 a & b 来计算 $a$ 和 $b$ 按位与运算的结果。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个数：$a_1\sim a_n$。

第三行 $m$ 个数：$b_1\sim b_m$。

输出格式

一个整数，即第二组里有几个这样的数。

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

2

样例 1 解释

只有 $5,7$ 满足要求，所以输出 $2$

3 4
3 3 3
7 7 7 7

4

样例 2 解释

可能有重复的数。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$0\le a_i,b_i\lt 2^{30}$。

• 子任务 1（30 分）：保证 $0\le a_i,b_i\le 1$。
• 子任务 2（30 分）：保证 $n,m\le 1000$。
• 子任务 3（40 分）：没有特殊限制。