#P17753. 永恒之夜
永恒之夜
题目描述
feluamn 需要一些魔力晶板,来驱散路途的黑暗。现在feluamn 有n 块魔力晶板,每块晶板上有m 个魔力槽,从1 到m 标号。一些魔力槽中可能有魔力水晶。feluamn 需要第 个位置上有魔力水晶,而其他位置没有水晶的魔力晶板。所以她需要取下一些魔力水晶。由于黑暗诅咒的关系,当第i 个位置的水晶被取下后,第 个位置上的魔力水晶也会随之掉落。
特别的,如果 的某个位置上没有魔力水晶,这个魔力水晶就不能被取下。并且水晶一旦离开魔力晶板就无法再安装上去了。
feluamn 希望能有尽量多的魔力晶板,以备旅途上的不测。由于空间水晶的存在,feluamn 并不需要担心衣兜不够大。但她忙于将FMT 融会贯通,以更好地对付黑暗,并没有时间来考虑这个问题。如果你能告诉她答案,这个可爱又善良的女孩子会对你感激不尽。
输入格式
从标准输入读入。
为了便于输入输出,约定用一个十进制整数来表示魔力晶板的状态。这个整数的二进制下第i 位为1 ,则表示魔力晶板的第i + 1 个位置有魔力水晶,反之则没有。
第一行一个正整数T ,表示数据组数。
对于每组数据,第一行两个正整数n ,m ,意义如问题描述中所述。
接下来n 行,每行一个整数表示feluamn 拥有的魔力晶板的状态。
接下来一行一个非负整数c ,意义如问题描述中所述。
接下来一行c 个正整数,第i 个正整数表示 。
接下来一行一个正整数q ,表示询问数量。
接下来q 行,每行一个非负整数表示feluamn 所需的魔力晶板的状态。
输出格式
输出到标准输出。
对于每组数据,输出q 行。第i 行一个非负整数表示第i 个询问的答案。
注意不同的数据之间不需要用空行隔开。
样例
样例1 输入
1
2 3
7
6
1
1
1
1
样例1 输出
1
样例1 解释
feluamn 需要状态为100 的魔力晶板,她有111 和011 两种晶板。只有111这个晶板取下第二个水晶才是feluamn 需要的。
样例2 输入
1
2 4
3
12
1
1
1
0
样例2 输出
2
数据范围与约定
对于所有数据,T ⩽5 ,1 ⩽q, n ⩽100000 ,1 ⩽m ⩽20 ,1 ⩽ ⩽m ,c < m 。保证代表魔力晶板状态的整数不超过m 位。相同的 只算一个。
• subtask1(20%): 1 ⩽q, n ⩽1000 ;
• subtask2(20%): 1 ⩽m ⩽7 ;
• subtask3(30%): c = 0 ;
• subtask4(30%): 没有特殊限制。