题目描述
Yazid 喜欢吃大碗宽面。现有 m 碗宽面,其中第 i 碗宽面(1≤i≤m)共包含 ni 根面条,它们的宽度分别为 Ai,1,Ai,2,…Ai,ni。
记 f(u,v) 表示若混合第 u 碗宽面和第 v 碗宽面,将得到的超大碗宽面的第 ⌊2nu+nv+1⌋ 小的面条宽度(⌊x⌋ 表示不超过 x 的最大整数)。
Yazid 想求出所有 f(u,v),但为了节省你的输出时间,你只需要对所有 1≤u≤m 求出:
- R(u)=v=1xorm(f(u,v)+u+v)(xor 指异或运算,在 C++ 语言中对应 \large{\tt{\text{^}}} 运算符)。
输入格式
第一行一个正整数 m,表示宽面碗数。
接下来 m 行,每行若干个用单个空格隔开的整数描述一碗宽面:这部分的第 i 行的第一个正整数为 ni,表示第 i 碗宽面包含的面条数;接下来 ni 个非负整数 Ai,1,Ai,2,…Ai,ni 描述各面条的宽度。
保证 m≤10000,ni≤500,0≤Ai,j≤109。
输出格式
输出 n 行,每行一个整数,其中第 i 行的整数为 R(i)。
样例
3
3 1 2 3
3 3 4 5
2 4 2
4
7
7
R(1)=(f(1,1)+2)xor(f(1,2)+3)xor(f(1,3)+4)=4xor6xor6=4
R(2)=(f(2,1)+3)xor(f(2,2)+4)xor(f(2,3)+5)=6xor8xor9=7
R(3)=(f(3,1)+4)xor(f(3,2)+5)xor(f(3,3)+6)=6xor9xor8=7