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 space-separated integers $N$ and $Q$. - The second line contains $N$ space-separated 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 space-separated 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$.
|Tags||basic-math, bits, march20, saurabhshadow, simple, tmwilliamlin|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.