Description

Yazid likes to eat big bowl wide noodles. Now there are $m$ bowls of wide noodles. In the $i$-th bowl of wide noodles ($1 \le i \le m$), there are $n_i$ noodles in total, and their widths are $A_{i,1},A_{i,2},\cdots,A_{i,n}$.

Let $f(u,v)$ denote the width of the $\left\lfloor\dfrac{n_u +n_v +1}{2}\right\rfloor$-th smallest noodle after mixing the $u$-th bowl of wide noodles and the $v$-th bowl of wide noodles to get an extra-large bowl of wide noodles ($\lfloor x \rfloor$ denotes the greatest integer not exceeding $x$).

Yazid wants to find all $f(u,v)$, but to save your output time, you only need to compute for all $1 \le u \le m$:

• $R(u)=\mathop{\rm xor}\limits_{v=1}^{m} {(f(u,v)+u+v)}$ ($\rm xor$ means the bitwise XOR operation, which corresponds to the ^ operator in C++).

Input Format

The first line contains a positive integer $m$, representing the number of bowls of wide noodles.

The next $m$ lines describe one bowl of wide noodles per line using several integers separated by single spaces: on the $i$-th line, the first positive integer is $n_i$, meaning the number of noodles in the $i$-th bowl; then $n_i$ non-negative integers $A_{i,j}$ describe the widths of the noodles.

Output Format

Output $m$ lines, each containing one integer. The integer on the $i$-th line should be $R(i)$.

3
3 1 2 3
3 3 4 5
2 4 2

4
7
7

Hint

Sample Explanation

For sample $1$:

• $\def\x{\operatorname{xor}} R(1) = {(f(1,1)+2)}\x{(f(1,2)+3)}\x{(f(1,3)+4)} = 4\x6\x6 = 4$
• $\def\x{\operatorname{xor}} R(2) = {(f(2,1)+3)}\x{(f(2,2)+4)}\x{(f(2,3)+5)} = 6\x8\x9 = 7$
• $\def\x{\operatorname{xor}} R(3) = {(f(3,1)+4)}\x{(f(3,2)+5)}\x{(f(3,3)+6)} = 6\x9\x8 = 7$

Constraints

For $100\%$ of the testdata, $m \le 10^4$, $n_i \le 500$, $0 \le A_{i,j} \le 10^9$.

Notes

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Solutions and other resources can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5