题目描述

Yazid 喜欢吃大碗宽面。现有 $m$ 碗宽面，其中第 $i$ 碗宽面（$1 \le i \le m$）共包含 $n_i$ 根面条，它们的宽度分别为 $A_{i,1},A_{i,2},\cdots,A_{i,n}$。

记 $f(u,v)$ 表示若混合第 $u$ 碗宽面和第 $v$ 碗宽面，将得到的超大碗宽面的第 $\left\lfloor\dfrac{n_u +n_v +1}{2}\right\rfloor$ 小的面条宽度（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。

Yazid 想求出所有 $f(u,v)$，但为了节省你的输出时间，你只需要对所有 $1 \le u \le m$ 求出：

• $R(u)=\mathop{\rm xor}\limits_{v=1}^{m} {(f(u,v)+u+v)}$（$\rm xor$ 指异或运算，在 C++ 语言中对应 ^ 运算符）。

输入格式

第一行一个正整数 $m$，表示宽面碗数。

接下来 $m$ 行，每行若干个用单个空格隔开的整数描述一碗宽面：这部分的第 $i$ 行的第一个正整数为 $n_i$，表示第 $i$ 碗宽面包含的面条数；接下来 $n_i$ 个非负整数 $A_{i,j}$ 描述各面条的宽度。

输出格式

输出 $n$ 行，每行一个整数，其中第 $i$ 行的整数为 $R(i)$。

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

4
7
7

提示

样例说明

对于样例 $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$

数据规模与约定

对于 $100\%$ 的数据，$m \le 10^4$，$n_i \le 500$，$0 \le A_{i,j} \le 10^9$。

说明

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。