#1709. 「THUPC 2019」大碗宽面 / median

「THUPC 2019」大碗宽面 / median

题目描述

Yazid 喜欢吃大碗宽面。现有 mm 碗宽面,其中第 ii 碗宽面(1im1\leq i\leq m)共包含 nin_i 根面条,它们的宽度分别为 $A_{\large i,1},A_{\large i,2},\dots A_{\large i,n_{\large i}}$。

f(u,v)f(u,v) 表示若混合第 uu 碗宽面和第 vv 碗宽面,将得到的超大碗宽面的nu+nv+12\left\lfloor\frac{n_u +n_v +1}{2}\right\rfloor的面条宽度(x\lfloor x\rfloor 表示不超过 xx 的最大整数)。

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

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

输入格式

第一行一个正整数 mm,表示宽面碗数。

接下来 mm 行,每行若干个用单个空格隔开的整数描述一碗宽面:这部分的第 ii 行的第一个正整数为 nin_i,表示第 ii 碗宽面包含的面条数;接下来 nin_i 个非负整数 Ai,1,Ai,2,Ai,niA_{i,1},A_{i,2},\dots A_{i,n_i} 描述各面条的宽度。

保证 m10000m\leq 10000ni500n_i\leq 5000Ai,j1090\leq A_{i,j}\leq 10^9

输出格式

输出 nn 行,每行一个整数,其中第 ii 行的整数为 R(i)R\left(i\right)

样例

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

$\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$