XOR Engine

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/MARCH20/hindi/ENGXOR.pdf), [Bengali](http://www.codechef.com/download/translated/MARCH20/bengali/ENGXOR.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/MARCH20/mandarin/ENGXOR.pdf), [Russian](http://www.codechef.com/download/translated/MARCH20/russian/ENGXOR.pdf), and [Vietnamese](http://www.codechef.com/download/translated/MARCH20/vietnamese/ENGXOR.pdf) as well. A sophomore Computer Science student is frustrated with boring college lectures. Professor X agreed to give him some questions; if the student answers all questions correctly, then minimum attendance criteria will not apply to him. Professor X chooses a sequence $A_1, A_2, \ldots, A_N$ and asks $Q$ queries. In each query, the student is given an integer $P$; he has to construct a sequence $B_1, B_2, \ldots, B_N$, where $P \oplus A_i = B_i$ for each valid $i$ ($\oplus$ denotes bitwise XOR), and then he has to find the number of elements of this sequence which have an even number of $1$s in the binary representation and the number of elements with an odd number of $1$s in the binary representation. Help him answer the queries. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $Q$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  $Q$ lines follow. Each of these lines contains a single integer $P$ describing a query. ### Output For each query, print a single line containing two spaceseparated integers ― the number of elements with an even number of $1$s and the number of elements with an odd number of $1$s in the binary representation. ### Constraints  $1 \le T \le 100$  $1 \le N, Q \le 10^5$  $ T \cdot (N+Q) \leq 4 \cdot 10^6 $  $1 \le A_i \le 10^8$ for each valid $i$  $1 \le P \le 10^5$ **The input/output is quite large, please use fast reading and writing methods.** ### Subtasks **Subtask #1 (30 points):** $N, Q \le 1,000$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 1 6 1 4 2 15 9 8 8 3 ``` ### Example Output ``` 2 4 ``` ### Explanation **Example case 1:** The elements of the sequence $B$ are $P \oplus 4 = 7$, $P \oplus 2 = 1$, $P \oplus 15 = 12$, $P \oplus 9 = 10$, $P \oplus 8 = 11$ and $P \oplus 8 = 11$. The elements which have an even number of $1$s in the binary representation are $12$ and $10$, while the elements with an odd number of $1$s are $7$, $1$, $11$ and $11$.Author:  saurabhshadow 
Editorial  https://discuss.codechef.com/problems/ENGXOR 
Tags  basicmath, bits, march20, saurabhshadow, simple, tmwilliamlin 
Date Added:  14102019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 