测试数据来自 system/1992

描述

给定一个长度为\(n\)的序列\(a_0,a_1,\cdots,a_{n-1}\)以及一个长度为\(m\)的序列\(b_0,b_1,\cdots,b_{m-1}\)。

求\(\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}gcd(a_i,b_j)~xor~i~xor~j\)是多少。因为答案可能很大，你只需要输出答案对\(2^{32}\)取模 的结果即可。注意\(gcd(0,x)=x\)且\(gcd(0,0)=0\)。

格式

输入格式

第一行包含两个正整数\(n,m\)满足\(1\le n,m\le 2000\)，表示序列的长度。
第二行包含\(n\)个正整数，表示\(a_0,a_1,\cdots,a_{n-1}\)满足\(0\le a_i\le 10^6\)。
第三行包含\(m\)个正整数，表示\(b_0,b_1,\cdots,b_{n-1}\)满足\(0\le b_i\le 10^6\)。

输出格式

输出一行一个整数，即答案。

样例1

样例输入1

3 2
5 9 6
3 4

样例输出1

6

样例2

样例输入2

2 2
8 9
0 6

样例输出2

22

样例3

样例输入3

1 1
9
6

样例输出3

3

限制

每一个测试点时间限制为0.3秒。

来源

感谢 Claris 提供。