# And-Or Game ORAND SOLUTION Code Chef

Page Contents

## And-Or Game ORAND SOLUTION Code Chef

And-Or Game ORAND SOLUTION  Chef is bored so he decided to play a game with two sets of numbers A and B of sizes N and M and an integer V initially equal to 0. Chef will play for a number of turns (possibly zero). Every turn in this game Chef will do one of the following operations:
Pick an integer X from the set A and assign V with V|X i.e the bitwise oring of the two numbers.And-Or Game ORAND SOLUTION
Pick an integer X from the set B and assign V with V&X i.e the bitwise anding of the two numbers.
Chef will stop playing when he gets bored. Find the number of values V can become when the game ends.

Input:
• First line will contain T, number of testcases. Then the testcases follow.
• The first line of each test case contains 2 space-separated integers, N and M.
• The second line contains N integers, A1, A2, …, AN
• The third line contains M integers, B1, B2, …, BM
Output:
For each test case, Print the number of values V can become.

Constraints
• 1≤N,M≤220
• 0≤Ai,Bi<220
• The sum of N over all cases in a subtask doesn’t exceed 220.
• The sum of M over all cases in a subtask doesn’t exceed 220.
• The elements in A are pairwise distinct.
• The elements in B are pairwise distinct.
Subtasks
• 30 points (time limit 2s): 1≤N,M≤210 and 0≤Ai,Bi<210.
• 30 points (time limit 2s): 1≤N,M≤215 and 0≤Ai,Bi<215.
• 40 points (time limit 5s): 1≤N,M≤220 and 0≤Ai,Bi<220.
Sample Input:
3
3 1
5 12 14
15
6 1
0 1 3 6 12 14
1
4 3
1 3 5 6
3 6 10
Sample Output:
6
9
8
EXPLANATION:
• In the first test case, V can reach values [0,5,12,13,14,15].
• In the second test case, V can reach values [0,1,3,6,7,12,13,14,15].
• In the third test case, V can reach values [01,2,3,4,5,6,7].

### 5 thoughts on “And-Or Game ORAND SOLUTION Code Chef”

error: Content is protected !!