One day when you were sitting in the couch and eating chips, a guy called you, who claimed that his name was Cuber QQ and he had your girlfriend kidnapped. This seems quite unlikely to you because you do not even have a girlfriend. However, to kill the boring time of Sunday afternoon, you asked how much the ransom is. Surprisingly, Cuber QQ is not interested in your money, the ransom is the answer to a matching problem. It turns out that Cuber QQ is a lover of binary operators, xor especially.
First of all, he shall give you a pair of sequences a and b, with length n and m respectively.
Given that a and b do not necessarily have the same length, they do not exactly make a pair. Therefore consecutive subsequences of a are used to make pairs with b, That makes n−m+1 pairs: al,al+1,…,al+m−1 and b for all 1≤l≤n−m+1.
For each pair (al,al+1,…,al+m−1;b), we say they are xor-matched if their pairwise-xor's are all available in a pre-defined set S. Concretely, the pair is a match if and only if al+i−1⊕bi∈2S⊕ of all 1≤i≤m. 2S⊕ is defined as the set of all possible xor-sum of S's subsets, i.e.,
2S⊕={t|t=⨁w∈Xw,X⊆S}
Note that, since {} is always a valid subset of S, 0 is always included in 2S⊕.
Now Cuber QQ wants you to tell him, for which l's, al,al+1,⋯,al+m−1 makes a match with b. He is not sending your illusory girlfriend back before you correctly answer his question.
输入格式
The first line contains an integer T (1≤T≤2⋅104), denotes the number of test cases.
Each test case begins with three space-separated integers n (1≤n≤2⋅105), m (1≤m≤min(n,5⋅104)) and k (1≤k≤100), denoting the lengths of a, b and the size of S.
The next line contains n space-separated integers a1,a2,⋯,an (0≤ai<230).
The next line contains m space-separated integers b1,b2,⋯,bm (0≤bi<230).
The last line contains k space-separated integers S1,S2,⋯,Sk (0≤Si<230).
It is guaranteed that ∑n≤1.2⋅106,∑m≤3⋅105,∑k≤6⋅105.