#CH0309P2395. 身份确认

身份确认

Cannot parse: 5000ms error parsing memory

Description

截至2008年5月23日12时,汶川大地震已经造成了55740人遇难,并且仍有数万人被掩埋在废墟之下。随着时间的推移,被埋和失踪者生还的希望越来越渺茫,而越来越多的遇难者的遗体开始成为卫生防疫工作最大的敌人。俗话说,大灾之后必有大疫,所以,如何防止疫情传播,尽量提高生还者的生存率,成了当前最重要的任务。于是,抗震救灾指挥部发布命令,对于发现的遇难者遗体,不再留存等待家属辨认,而是记录其体貌特征并留存DNA样本后,就地消毒深埋或火化。

北京大学生命科学学院青年志愿者小分队是赶赴灾区负责DNA样本提取及识别的队伍之一,而你,则是队伍中的特派程序员。随着提取到的DNA样本量的增加以及心急如焚的家属们的辨认请求数的增加,如何快速进行匹配检验成了当前最大的难题。

每个遇难者的DNA特征都可以用一个30位二进制整数来描述,为了方便存储,通常将其转化为10进制来记录。根据专家的研究结果,两个人有亲属关系,当且仅当他们的DNA特征对应的二进制整数按位异或得到的二进制整数中,有且仅有两个数位上为1。

现在,你的任务是写一个程序,输入遇难者DNA数据库以及请求辨认的家属的DNA数据库,询问它们两个数据库之间有多少对亲属关系。

Input Format

第一行包含两个整数N, M,分别代表遇难者和家属的数量。
接下来的N行,每行一个整数Vi,表示遇难者的DNA特征对应的整数。
接下来的M行,每行一个整数Fi,表示家属的DNA特征对应的整数。

Output Format

仅包含一个整数,表示亲属关系的数量。

2 1
9
7
5

1

Hint

2 ≤ N, M ≤ 100000, 0 ≤ Vi,Fi < 230

Source

Palmtenor