問題 G - snowy bunny

Time Limit: 2 seconds / Memory Limit: 256 MB

問題

ゆきうさぎは二進法での計算が好きである.今日は,「ゆきうさぎ変換」という非負整数の変換を考えている.

「ゆきうさぎ変換」は,2M 未満の非負整数を受け取り,2N 未満の非負整数を返す.「ゆきうさぎ変換」は,20 の位,21 の位,…,2M-1 の位の M 個について,その「ゆきさき」を決めることで定まる.各「ゆきさき」は,20 の位,21 の位,…,2N-1 の位の N 個のうちのいくつか (0 個でもすべてでもよい) である.ここで,M 個の「ゆきさき」を合わせると,N 個の位をちょうど 1 回ずつ選んでいなければならない.次の図は M = 5,N = 6 のときの「ゆきうさぎ変換」の例を表している.

「ゆきさき」を定めると,「ゆきうさぎ変換」がどんな数を返すかは自然に決まる.M 個の位の 0 または 1 を,それぞれ「ゆきさき」のところにそのまま書き込んだものが,返される値である.次の図は,上の図の「ゆきうさぎ変換」で 19 (二進法で 10011) が 60 (二進法で 111100) になる様子を示している.

ゆきうさぎには,「かっこいい」と思っている数や,「かわいい」と思っている数がそれぞれいくつかある.これらは以下の特徴を持っている.

ここで,ANDOR はビット演算の AND や OR である.すなわち,二進法の各桁ごとに論理積や論理和を計算した値を表す.以下に例を示す.

ゆきうさぎは,「かっこいい」と思っている数を受け取ったとき必ず「かわいい」と思っている数を返すような「ゆきうさぎ変換」が大好きである.そのような「ゆきうさぎ変換」が何通りあるかをぜひ知りたい.

入力

入力の 1 行目はテストケースの個数を表す整数 T を含む.以下 T 個のテストケースが続く.

M N A B
X1 ... XA
Y1 ... YB

各テストケースの 1 行目は 4 つの整数 M, N, A, B を含む.

各テストケースの 2 行目は A 個の整数 X1, …, XA を含む.これらはゆきうさぎが「かっこいい」と思っている数を表す.

各テストケースの 3 行目は B 個の整数 Y1, …, YB を含む.これらはゆきうさぎが「かわいい」と思っている数を表す.

出力

各テストケースごとに,ゆきうさぎが「かっこいい」と思っている数を受け取ったとき必ず「かわいい」と思っている数を返すような「ゆきうさぎ変換」の個数を 1 行に出力せよ.

制約

部分点

100 点中 25 点分のデータは以下を満たす.

入出力例

入力例 1

3
3 2 4 3
2 3 6 7
0 1 3
3 4 8 16
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 4 8 4
0 1 2 3 8 9 10 11
0 2 4 6

出力例 1

5
81
16

1 つ目のテストケースにおいては,以下の 5 通りの「ゆきうさぎ変換」が条件を満たす.

2 つ目のテストケースにおいては,M = 3,N = 4 のときのすべての「ゆきうさぎ変換」が条件を満たす.

入力例 2

2
5 6 6 11
2 3 14 15 19 31
0 2 16 18 19 20 22 23 60 62 63
10 6 1 1
776
34

出力例 2

330
21609

Problem Setter: hos