题目描述

给定序列 $\{a_n\},\{b_n\}$，有 $m$ 次询问，

每次询问给定 $k$，求 $\sum\limits_{i=1}^n[(a_i\oplus k)\le b_i]$，其中 $\oplus$ 是按位异或。

本题部分测试点强制在线。

输入格式

第一行三个整数 $T,n,m$，$T=1/0$ 表示这组数据是/否强制在线。

第二行 $n$ 个整数 $\{a_n\}$。

第三行 $n$ 个整数 $\{b_n\}$。

接下来 $m$ 行，每行一个整数 $k'$，表示一次询问 $k=k'\oplus(l\times T)$，

其中 $l$ 是上次询问的答案，第一次询问时 $l=0$。

输出格式

$m$ 行每行一个整数，表示每次询问的答案。

1 1 1
1
1
1

1

0 5 5
3 1 4 0 2
3 7 2 5 1
0
2
3
5
7

3
4
4
3
1

1 5 5
3 1 4 0 2
3 7 2 5 1
0
1
7
1
4

3
4
4
3
1

提示

本题采用捆绑测试。

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