Parity Again

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JULY19/hindi/PRTAGN.pdf), [Bengali](http://www.codechef.com/download/translated/JULY19/bengali/PRTAGN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JULY19/mandarin/PRTAGN.pdf), [Russian](http://www.codechef.com/download/translated/JULY19/russian/PRTAGN.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JULY19/vietnamese/PRTAGN.pdf) as well. You are given a set $S$ and $Q$ queries. Initially, $S$ is empty. In each query:  You are given a positive integer $X$.  You should insert $X$ into $S$.  For each $y \in S$ before this query such that $y \neq X$, you should also insert $y \oplus X$ into $S$ ($\oplus$ denotes the XOR operation).  Then, you should find two values $E$ and $O$: the number of elements of $S$ with an even number of $1$s and with an odd number of $1$s in the binary representation, respectively. Note that a set cannot have duplicate elements, so if you try to insert into $S$ an element that is already present in $S$, then nothing happens. ### 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 a single integer $Q$.  Each of the next $Q$ lines contains a single integer $X$ describing a query. ### Output For each query, print a single line containing two spaceseparated integers $E$ and $O$. ### Constraints  $1 \le T \le 5$  $1 \le Q, X \le 10^5$ ### Subtasks **Subtask #1 (30 points):**  $1 \le Q \le 1,000$  $1 \le X \le 128$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 1 3 4 2 7 ``` ### Example Output ``` 0 1 1 2 3 4 ``` ### Explanation **Example case 1:**  Initially, the set is empty: $S = \{\}$.  After the first query, $S = \{4\}$, so there is only one element with an odd number of $1$s in the binary representation ("100").  After the second query, $S = \{4,2,6\}$, there is one element with an even number of $1$s in the binary representation ($6$ is "110") and the other two elements have an odd number of $1$s.  After the third query, $S = \{4,2,6,7,3,5,1\}$.Author:  prnjl_rai 
Editorial  https://discuss.codechef.com/problems/PRTAGN 
Tags  adhoc, easy, july19, longchallenge, prnjl_rai, xor 
Date Added:  21052019 
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, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions